OI教程之数论

\author{张若天}
\institute{清华大学}
\date{\today}

附属于/oi

推荐网站projecteuler.net

素数/质数(prime number)

大于1且因子只有1和本身。

算数基本定理

任何一个大于1的自然数$N$,如果$N$不为质数,那么N可以唯一分解成有限个质数的乘积$N=P_1^{a_1}P_2^{a_2}P_3^{a_3}\ldots P_n^{a_n}$,这里$P_1<P_2<P_3 \ldots < P_n$均为质数,其中指数$a_i$是正整数。

素数定理

$$\pi(n) \sim \frac{n}{\ln(n)} $$
$\pi(n)$是不大于$n$的素数数量。

  • 判断一个数字是否为素数。 O($\sqrt{n}$)
  • 埃氏筛法 O($nlogn$)/O($nloglogn$)

    1
    2
    3
    4
    5
    6
    7
    8
    for(int i=2;i<=n;i++){
    if(!notprime[i]){
    prime[tot++] = i;
    for(int j=i*i;j<=n;j+=i){
    notprime[j] = true;
    }
    }
    }
  • 线性筛法 O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for(int i=2;i<=n;i++){
    if(!mindiv[i]){
    mindiv[i]=i;p[tot++]=i;
    }
    for(int j=0;p[j]*i<=n;j++){
    mindiv[p[j]*i]=p[j];
    if(mindiv[i]==p[j]){
    break;
    }
    }
    }

欧几里得算法(辗转相除法/Euclid’s algorithm)

  • gcd: 最大公约数。(a,b) = gcd(a,b) (唯一分解后指数取min)
  • lcm: 最小公倍数。[a,b] = lcm(a,b) (唯一分解后指数取max)
  • (a,b)[a,b] = ab

gcd(a,b) = b==0?a:gcd(b,a%b)
证明? hint: a=bq+r, 然后运用数学归纳法

裴蜀定理(Bezout’s Identity)

  • $(a,b) = d \Rightarrow ax+by = d$
  • $(a,b) = 1 \Leftrightarrow ax+by = 1$
    若 a,b 是整数, 且(a,b)=d,那么对于任意的整数 x,y,ax+by 都一定是 d的倍数,特别地,一定存在整数 x,y,使 ax+by=d 成立。

可以用之后的扩展欧几里得算法证明。

扩展欧几里得算法(Extended Euclidean Algorithm/exgcd)

  • a = 1, b = 0 时有 x=1,y=0。(归纳法的基础条件)
  • 对于 b,a%b的x’,y’能不能得到a,b的x,y?
  • $ a % b = a-[a/b]*b$
  • x’= y-[a/b]*x , y’ = x
1
2
3
4
5
6
7
int exgcd(int a,int b,int &x,int &y){
int t;
if(!b) {x=1;y=0;return a;}
t=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return t;
}

推广

给定a,b,c,求$ax+by=c$的一组x,y解。

例题: POJ1061/BZOJ1477 青蛙的约会

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

例题: NOIP 2012 同余方程

求关于 x的同余方程 $ax % b = 1$ 的最小正整数解。
输入数据保证一定有解。

费马小定理

若p为素数。(a,p)=1。

$$ a^{p-1} \equiv 1 \mod{p} $$

乘法逆元

$ab = 1 \ (mod \ p)$
$b = a^{-1}$

有了乘法逆元可以在模意义下做除法。

  • Exgcd求法
  • 费马小定理求法
  • O(p)求1-p每个数字逆元

中国剩余定理

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
解同余方程组。

  • 传统方法(构造,类似拉格朗日插值法)
  • 利用exgcd两两合并

例题: POJ 1006 Biorhythms

人自出生起就有体力,情感和智力三个生理周期,分别为23,28和33天。一个周期内有一天为峰值,在这一天,人在对应的方面(体力,情感或智力)表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期,分别对应于体力,情感,智力出现峰值的日期。然后再给出一个起始日期,要求从这一天开始,算出最少再过多少天后三个峰值同时出现

欧拉定理

推广费马小定理可以得到欧拉定理。
剩余系,简系定义。
模m简系大小记作$\phi(m)$。
如果(a,m)=1,$a^{\phi(m)} = 1(mod\ m)$
证明:hint: 考虑剩余系构成的集合,每个数乘 a 构成的集合是原集合的一个 置换。这两个集合的乘积相等。

欧拉函数

$\phi(x)$

如何计算欧拉函数?
线性筛:
$\phi(p^k) = p^k - p^{k-1}= (p-1) p^{k-1}$
(a,b)=1
$\phi(ab) = \phi(a) \phi(b)$

一些额外的东西

阶: 最小的k满足 $a^k = 1 (mod p)$,一定是$\phi(p)$的约数。
原根与指标。
BSGS求离散对数。

简单反演

积性函数

if gcd(p,q)==1:
f(pq)=f(p)*f(q)。
id,e,1,$\phi$,$\mu$,$d$,$\sigma$。

推荐ppt,PoPoQQQ《莫比乌斯反演》

Dirichlet积

狄利克雷卷积是一种对整数数论函数用约数关系进行的特殊的卷积。
(f*g)(N)=f(N)*g(N)
($f \times g$)(N) =$ \sum_{d|N}{f(d)*g(\frac{N}{d})}$
如果f、g均为积性,f*g,fxg也均为积性。

几个等式:
$f = f \times e$
$id = \phi \times 1$
$e = \mu \times 1$

$\sum_{i=1}^N {e(gcd(i,N))}$
$ = \sum_{i=1}^N \sum_{d|gcd(i,n)}{\mu(d)} $
$= \sum_{i=1}^N \sum_{d|i \& d|n} {\mu(d)}$
$= \sum_{d|N}{\mu(d) * N/d}$
$= \mu \times id$

莫比乌斯反演

$F = f \times 1$
两边同乘$\mu$
$F \times \mu = f \times 1 \times \mu$
$F \times \mu = f \times e = f$
从第一个式子到第三个式子也叫莫比乌斯反演。

1D gcd sum

$\sum_{i=1}^{N}{gcd(i,N)}$
$= \sum_{i=1}^{N}{\sum_{d|gcd(i,N)}{\phi(d)} }$
$= \sum_{i=1}^{N}{\sum_{d|i and d|n}{\phi(d)} }$
$= \sum_{d|N}{\phi(d)*\frac{N}{d} }$

2D gcd sum

$\sum_{i=1}^N \sum_{j=1}^M {gcd(i,j)}$ \p
$= \sum_{i=1}^N \sum_{j=1}^M \sum_{d|gcd(i,j)}{\phi(d)}$
$= \sum_{i=1}^N \sum_{j=1}^M \sum_{d|i \& d|j} \phi(d)$
$= \sum_{d \le N} \phi(d) [N/d] [M/d]$

zap

对于给定的整数N,M和d,有多少正整数对x,y,满足x<=N,y<=M,并且gcd(x,y)=d。
等价于x<=N/d,y<=M/d,互质的x,y的对数。

$\sum_{i=1}^{N}{\sum_{j=1}^{M}{e(gcd(i,j))} }$
$=\sum_{i=1}^{N}{\sum_{j=1}^{M}{\sum_{d|gcd(i,j)}{\mu(d)} } }$
$=\sum_{i=1}^{N}{\sum_{j=1}^{M}{\sum_{d|i and d|j}{\mu(d)} } }$
$=\sum_{d \le N}{\mu(d) \times \lfloor \frac{N}{d} \rfloor}$

与N互素数的和

$\sum_{i \le n \& gcd(n,i)=1} i$
$=\sum_{i \le n} i e(gcd(n,i))$
$=\sum_{i \le n} (i \sum_{d|gcd(n,i)}{\mu(d)})$
$=\sum_{d|n}(\mu(d) \sum_{i \le n, d|i}i)$
$=\sum_{d|n} \mu(d) (\frac{n(n/d+1)}{2})$
$= n/2 (\mu \times id + \mu \times 1)$
$= n/2 (\phi + e)$
$ = \frac{(id*\phi + e)}{2}$

其他题目

BZOJ2045: 双亲数
BZOJ2301: [HAOI2011]Problem b
BZOJ3529: [Sdoi2014]数表
BZOJ2818: Gcd
BZOJ2820: YY的GCD

任何形式的使用、转载请注明出处!

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框