NOIP数论内容整理
注：特别感谢sdsy的zxy神仙以及lcez的tsr神仙帮助审稿
一、整除：
对于\(a,b~\in~Z\)，若\(\exists~k~\in~Z\),\(s.t.~b~=~k~\times~a\)，则说\(a\)整除\(b\)，记做\(a~|~b\)
二、带余除法：
\(~\forall~a,b~\in~z\)存在且仅存在唯一的\(q,r~\in~Z^*\)，\(s.t.~b~=~q~\times~a+r\)，其中\(r~\in~[0,a)\)。记做\(r~=~b~Mod~a\)。
三、公约数
设\(a,b~\in~Z\)，若\(~\exists~k,x,y~\in~Z^*\)，\(s.t.~a~=k~\times~x,b~=~k~\times~y\)，则说\(k\)是\(a,b\)的公约数。公倍数同理。
四、\(gcd\)与\(lcm\)
记\(a,b\)的最大公约数为\(gcd(a,b)\)，最小公倍数为\(lcm(a,b)\)
五、最大公约数与最小公倍数乘积性质定理
性质：\(a~\times~b=gcd(a,b)~\times~lcm(a,b)\)
六：最大公约数的求取：(以下不妨设\(b~\leq~a\))
其中，更相减损术的复杂度是\(O(n)\)，欧几里得算法的复杂度是\(O(logn)\)。其中\(n~=~\max(a,b)\)
七：更相减损术的优化
引理：\(\forall~m~\neq~0,~a,b~\in~Z\)，有\(m~\times~gcd(a,b)=gcd(ma,mb)\)
考虑两个奇数相减答案显然是偶数。于是一次更相减损术显然对应一个数除以2的操作。即更相减损的次数与除以二的操作次数同阶。考虑一个数最多被除\(log\)次。于是该算法的复杂度为\(O(logn)\)。
该算法常用在对两个高精度数求\(gcd\)，因为两个高精度数做除法的复杂度难以承受，从而应用该算法。
八、例题：
给定一个序列，要求支持区间加法。多次查询区间内所有数字的\(gcd\)。\(n,m,a_i~\leq~10^5\)
Solution:
因为区间加法无法维护\(gcd\)，所以显然不能暴力线段树。考虑对原序列做差分。由更相减损定理，显然成立\(gcd(a,b,c)~=~gcd(a,b-a,c-b)\)。于是差分后区间加法改为单点修改操作。于是一次操作的复杂度为\(O(log^2n)\)。总时间复杂度为\(O\left(m\log^2n\right)\)，可以通过本题。
九、扩展欧几里得算法
裴蜀定理：关于\(x,y\)的方程\(ax+by=c\)有解当且仅当\(gcd(a,b)|c\)。
求关于\(x,y\)的方程\(ax+by=c\)的一组整数解。
不妨设\(c=gcd(a,b)\)。否则左侧乘一常数\(k\)，不失一般性
根据欧几里得算法，有
\[gcd(a,b)=gcd(b,a~Mod~b)\]
于是有
\[ax+by=gcd(a,b)=gcd(b,a~Mod~b)=bx_0+(a~Mod~b)y_0\]
于是有
\[\begin{align}ax+by& = bx_0+(a-\left\lfloor\frac{a}{b}\right\rfloor~\times~b)y_0\\& = ay_0+b(x_0-\left\lfloor\frac{a}{b}\right\rfloor~y_0) \\\end{align}\]
根据对应系数相等，显然有\(x=y_0,y=x_0-\left\lfloor\frac{a}{b}\right\rfloor~y_0\)。考虑他的一组特解：当\(b=0\)时，显然\(x=1,y=0\)成立。
求上述方程的所有解
假设求出的该方程的一组特解\(x=x_0,y=y_0\)，则该方程的所有解为\(x=x_0+\frac{k~\times~b}{gcd(a,b)},y=y_0-\frac{k~\times~a}{gcd(a,b)}\)。
十、素数：
有且仅有\(1\)和本身两个因子的数是素数
十一、埃拉托色尼筛法：
对每个数只筛掉它的倍数。
int pcnt;
int prime[maxn];
bool is_not_prime[maxn];
void Get_Prime(int x) {
is_not_prime[1]=true;
for(int i=1;i<=x;++i) if(!is_not_prime[i]) {
prime[++pcnt]=i;
for(int j=i*i;j<=x;j+=i;) is_not_prime[j]=true;
}
}十二：欧拉筛法
对每个数只被他的最小素因子筛掉
int pcnt;
int prime[maxn];
bool is_not_prime[maxn];
void Get_Prime(int x) {
is_not_prime[1]=true;
for(int i=2;i<=x;++i) {
if(!is_not_prime[i]) prime[++pcnt];
for(int j=1;j<=pcnt;++j) {
if(i*prime[j] > x) break;
is_not_prime[i*prime[j]]=true;
if(!(i%prime[j])) break;
}
}
}十三：在\(O(nlogn)\)时间内筛除\(n\)以内所有数的素因子
对于每个数记录自己的最小素因子。对于第每个数，迭代将每个数除以自己的最小素因子。
int pcnt;
int prime[maxn],pre[maxn];
bool is_not_prime[maxn];
void Get_Prime(int x) {
is_not_prime[1]=true;
for(int i=2;i<=x;++i) {
if(!is_not_prime[i]) prime[++pcnt],pre[i]=pcnt;
for(rg int j=1;j<=pcnt;++j) {
if(i*prime[j] > x) break;
is_not_prime[i*prime[j]]=true;
pre[i*prime[j]]=j;
if(!(i%prime[j])) break;
}
}
}
void ans(int x) {
for(int i=1;i<=x;++i) {
printf("%d:",i);
int di=i;
while(di != 1) printf("%d",prime[pre[di]]),di/=prime[pre[di]];
putchar('\n');
}
}十四、唯一分解定理：
\(\forall~x~\in~Z^*\)，存在且仅存在一个形如\(x=p_1^{c_1}~p_2^{c_2}~...~p_k^{c_k}\)的等式。其中满足\(p_i ~<~p_{i+1},p_i\)为质数，\(c_i~\in~Z\)
则对于\(a,b\)的\(gcd,lcm\)，其唯一分解式对应位置的指数取\(\min,\max\)即为对应的\(gcd,lcm\)的唯一分解式
十五、欧拉phi函数：
定义：\(\phi(n)\)为\([1,n)\)中与\(n\)互质的数的个数
\(\phi(n)~=~n~(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\)
其中\(p_i\)为\(n\)的唯一分解式对应底数。
证明：不妨设\(n\)只有\(p,q\)两个因数。否则做数学归纳
则与\(n\)互质的数的个数为\(n\)减去\(p\)的倍数和\(q\)的倍数。根据容斥原理，应加回\((pq)\)的倍数。即
\[\begin{align}\phi(n)& = ~n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}\\& = ~n\left(1-\frac{1}{p}-\frac{1}{q}-\frac{1}{pq}\right)\\& = ~n\left(1-\frac{1}{p}\right) \left(1-\frac{1}{q}\right)\end{align}\]
对于\(n\)有更多因数的情况，可以依据唯一分解定理做数学归纳。证毕。
求单个数字的\(\phi\)函数：
暴力枚举质因数。复杂度\(O(\sqrt{n})\)
埃拉托色尼筛法：
对每个质数，修改他的倍数的\(phi\)函数值
int pcnt;
int prime[maxn],phi[maxn];
bool is_not_prime[maxn];
void euler(int x) {
for(int i=1;i<=x;++i) phi[i]=i;
for(int i=2;i<=x;++i) if(!is_not_prime[i]) {
prime[++pcnt]=i;phi[i]=i-1;
for(rg int j=i*i;j<=pcnt;j+=i) {
is_not_prime[j]=true;
phi[j]=phi[j]/i*(i-1);
}
}
}欧拉筛：
对每个数，只被他的最小质因子筛掉。
考虑通过一个质因子求出他的欧拉函数值。
引理：\(\forall x\)为质数，显然\(\phi(x)=x-1\)。
定理一：\(\forall~x~\in~Z^*,p|x\)，若\(\frac{x}{p}\)与\(p\)不互质，则\(\phi(x)=\phi(\frac{x}{p})~\times~p\)
证明：
不妨设 \(x\) 有且仅有 \(p,q\) 两个质因子，否则对\(q\)做数学归纳，不失一般性
则 \(q~=~\frac{x}{p}\)
于是由容斥原理有
\[\phi(x)~=~x~-~\frac{x}{p}~-~\frac{x}{q}~+~\frac{x}{pq}\]
\[\phi(\frac{x}{p})~=~\frac{x}{p}~-\frac{x}{p^2}~-~\frac{x}{pq}+~\frac{x}{p^2q}\]
上式除以下式，得
\[\frac{\phi(x)}{\phi\frac{x}{p}}=p\]
移项整理后，原式得证。
证毕。
定理二：\(\forall~x~\in~Z^*,p|x\)，若\(\frac{x}{p}\)与\(p\)互质，则\(\phi(x)=\phi(\frac{x}{p})~\times~(p-1)\)
证明：
易证\(phi\)函数为积性函数。因为\(\frac{x}{p}\)与\(p\)互质，于是\(\phi(x)=\phi(\frac{x}{p})~\times~\phi(p)\)
又因为\(p\)是一个质数，于是根据引理，\(\phi(p)=p-1\)。
原式得证。
证毕。
于是对于每个数，若他是质数，则应用引理，否则在筛时，若最小质因子与他互质，则应用定理二，否则应用定理一。
int pcnt;
int prime[maxn],phi[maxn];
bool is_not_prime[maxn];
void euler(int x) {
phi[1]=1;
is_not_prime[1]=true;
for(int i=1;i<=x;++i) {
if(!is_not_prime[i]) prime[++pcnt]=i,phi[i]=i-1;
for(int j=1;j<=pcnt;++j) {
if(i*prime[j] > x) break;
is_not_prime[i * prime[j]]=true;
if(!(i%prime[j])) {phi[i*prime[j]]=phi[i]*prime[j];break;}
else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}十六、模方程：
定义：\(\forall a,b ~\in~Z\)，若\(a~Mod~m~=~b~Mod~m\) 则称作\(a,b\)在模\(m\)域下同余。记做\(a~\equiv~b~(Mod~m)\)。
同余式两边支持同时加、减、乘同一个数字，但不支持除法。
十七、模逆元：
\(\forall~a~\in~Z\)，若\(\exists~x~\in~Z,s.t.~ax~\equiv~1~(Mod~m)\)则称\(x\)是\(a\)在模\(m\)域下的逆元。在模\(m\)域下，任何一个整数除以\(a\)完全等价于乘\(x\)。
一般而言，\(m\)为质数是\(a\)存在逆元的充分条件
十八、逆元的求法
单个数求逆元
解方程\(ax~\equiv~1~(Mod~m)\)，发现等价于\(ax+km=1\)。直接使用\(exgcd\)求得答案即可。
线性筛逆元：
记\(x\)的逆元为\(x^{-1}\)，数组表示为\(inv_x\)
则有线性递推式：\(inv_i~=~(-\left\lfloor\frac{m}{i}\right\rfloor~\times~inv_{m~Mod~i}+m)~Mod~m\)
证明：
对于所有的\(i\)，写出他的带余除法表达式：
\[m~=~ki~+~r,r~\in~[0,i)\]
在\(Mod~m\)域下有：
\[ki~+~r~\equiv~0~(Mod~m)\]
等式两侧同乘\(i^{-1}~\times~r^{-1}\)
化简，整理得到：
\[i^{-1}~\equiv~-kr^{-1} (Mod m)\]
因为\(k~=~\left\lfloor\frac{m}{i}\right\rfloor\)，原式得证。
int inv[maxn];
void Get_inv(int x,int p) {
inv[1]=1;
for(int i=2;i<=x;++i) inv[i]=(p-p/i)*inv[p%i]%p;
}