来自扶苏的整理授权
NOIP数论内容整理
一、整除：
对于(a,b~in~Z)，若(exists~k~in~Z),(s.t.~b~=~k~ imes~a)，则说(a)整除(b)，记做(a~|~b)
二、带余除法：
(~forall~a,b~in~z)存在且仅存在唯一的(q,r~in~Z)，(s.t.~b~=~q~ imes~a+r)，其中(r~in~[0,a))。记做(r~=~b~Mod~a)。
三、公约数
设(a,b~in~Z)，若(~exists~k,x,y~in~Z^*)，(s.t.~a~=k~ imes~x,b~=~k~ imes~y)，则说(k)是(a,b)的公约数。公倍数同理。
四、(gcd)与(lcm)
记(a,b)的最大公约数为(gcd(a,b))，最小公倍数为(lcm(a,b))
五、最大公约数与最小公倍数乘积性质定理
性质：(a~ imes~b=gcd(a,b)~ imes~lcm(a,b))
六：最大公约数的求取：
(以下不妨设(b~leq~a))
更相减损术：(gcd(a,b)~=~gcd(b,a-b))
欧几里得算法：(gcd(a,b)~=~gcd(b,a~Mod~b))
其中，更相减损术的复杂度是(O(n))，欧几里得算法的复杂度是(O(logn))。其中(n~=~max(a,b))
七：更相减损术的优化
引理：(forall~m~ eq~0,~a,b~in~Z)，有(m~ imes~gcd(a,b)=gcd(ma,mb))
当(a,b)是两个偶数时，显然(gcd(a,b))有一因数(2)。于是(gcd(a,b)~=~2~ imes~gcd(frac{a}{2},frac{b}{2}))
当(a,b)一奇一偶的时候，不妨设(a)是偶数。显然(gcd(a,b))不含因子(2)。于是有(gcd(a,b)=gcd(frac{a}{2},b))
当(a,b)同为奇数时，直接应用更相减损术。(gcd(a,b)=gcd(b,a-b))。
考虑两个奇数相减答案显然是偶数。于是一次更相减损术显然对应一个数除以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))。总时间复杂度为(Oleft(mlog^2n ight))，可以通过本题。
八、扩展欧几里得算法
裴蜀定理：关于(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$$
于是有
根据对应系数相等，显然有(x=y_0,y=x_0-leftlfloorfrac{a}{b} ight floor~y_0)。考虑他的一组特解：当(b=0)时，显然(x=1,y=0)成立。
求上述方程的所有解
假设求出的该方程的一组特解(x=x_0,y=y_0)，则该方程的所有解为(x=x_0+frac{k~ imes~b}{gcd(a,b)},y=y_0-frac{k~ imes~a}{gcd(a,b)})。
九、埃拉托色尼筛法：
对每个数只筛掉它的倍数。
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]=i;
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('
');
}
}
十二、唯一分解定理：
(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(x))为([1,n))中与(n)互质的数的个数
(phi(x)~=~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))的倍数。即
对于(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<=x;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})~ imes~p)
证明：
不妨设 (x) 有且仅有 (p,q) 两个质因子，否则对(q)做数学归纳，不失一般性
则 (q~=~frac{x}{p})
于是由容斥原理有
上式除以下式，得
移项整理后，原式得证。
证毕。
定理二：(forall~x~in~Z,p|x)，若(frac{x}{p})与(p)互质，则(phi(x)=phi(frac{x}{p})~ imes~(p-1))
证明：
易证(phi)函数为积性函数。因为(frac{x}{p})与(p)互质，于是(phi(x)=phi(frac{x}{p})~ imes~phi(p))
又因为(p)是一个质数，于是根据引理，(phi(p)=p-1)。（upd）
原式得证。
证毕。
于是对于每个数，若他是质数，则应用引理，否则在筛时，若最小质因子与他互质，则应用定理二，否则应用定理一。
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~=~(-leftlfloorfrac{m}{i} ight floor~ imes~inv_{m~Mod~i}+m)~Mod~m)
证明：
对于所有的(i)，写出他的带余除法表达式：
在(Mod~m)域下有：
等式两侧同乘(i^{-1}~ imes~r^{-1})
化简，整理得到：
因为由(①)式得(k~=~leftlfloorfrac{m}{i} ight floor)，(r=m~Mod~i)，带入(②)式原式得证。
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;
}
十七、模
模： 表示一个集合(Ssubseteq Z)，集合对加减法封闭
生成模: 集合(T)的生成模是，最小的模(S)，使得(Tsubseteq S)
实际意义：若(ain T,bin T,a+b otin T~~OR~~a-b otin T)，将(a+b,a-b)加入(T)。不断进行。
模(S)一定是某个数所有倍数的集合
证明：若(x)是(S)中的最小正整数
(~~~~~~~~~~)假设存在(y),不是(x)的倍数
(~~~~~~~~~~)取(r=ymod x),则(rin S)
(~~~~~~~~~~)那么(0<r<x)，矛盾。
(~~~~~~~~~~)因此，模(S)一定是某个数所有倍数的集合。
十八、群、环、域相关
群
群((G,cdot))
封闭性：(forall ain G, bin G, acdot b in G)
结合律：((acdot b)cdot c=acdot (bcdot c))
单位元（幺元）：(exists ein G), s.t. (forall ain G, ecdot a=acdot e=a)
逆元：(forall ain G, exists bin G), s.t. (acdot b=bcdot a=e)
举例：
(Qsetminus{0}, Rsetminus{0}, Csetminus{0})，所有行列式非0的(n)阶方阵组成一个群，{1,-1}
单位元唯一
设有两个单位元(e_1,e_2)
(e_1=e_1e_2=e_2)
逆元唯一
假设(a)有两个逆元(b,c)，那么
(b=b(ac)=(ba)c=c)
周期：(a)的周期是(o(a))
(o(a))表示最小正整数，使得(a^{o(a)}=e)
((ab)^{-1}=b^{-1}a^{-1})
(ab(b^{-1}a^{-1})=b^{-1}a^{-1}ab=e)
子群
若((G,cdot)),(Hsubseteq G), 且 ((H,cdot))是群，称在运算(cdot)下，(H)是(G)的子群，用(Hleq G)表示
生成子群: 集合(S)的生成子群用(<S>)表示
右傍集
如果(Hleq G)，对于(ain G)，定义集合(Ha={xin G~|~ exists hin H, ha=x})
(|H|=|Ha|)
如果(h_1 eq h_2)，那么(h_1a eq h_2a)
反证：若(h_1a=h_2a)，(h_1aa^{-1}=h_2aa^{-1},~h_1=h_2)矛盾
对于不同的(h)，(ha)互不相同，因此(|Ha|=|H|)
(Ha=Hb)当且仅当(ab^{-1}in H)
若(Ha=Hb)，则(eain Ha)，即(ain Hb)，那么(exists hin H,~a=hb),那么(ab^{-1}=h)
若(ab^{-1}in H)，那么(ha=ha(b^{-1}b)=h'bin Hb)，因此(Hasubseteq Hb)
(hb=hb(a^{-1}a)=h(ab^{-1})^{-1}ain Ha)，故(Hbsubseteq Ha)
因此(Ha=Hb)
若(Ha eq Hb)，那么(Hacap Hb = emptyset)
假设(xin Hacap Hb)， 则(exists h_1,h_2in H)，(h_1a=h_2b=x) ， 那么(ab^{-1}=h_1^{-1}h_2in H)，那么(Ha=Hb)，矛盾
由于(forall gin G)， (gin Hg)，所以(G)中每个元素都在某个傍集中。用([G:H])表示不同的傍集数，那么
(|G|=|H|cdot [G:H])
(|H|)是(|G|)的约数
若(ain G)，则(o(a)~~|~~|G|)
考虑(a)的生成子群(<a>={a,a^2,a^3,...a^{o(a)}})
考虑质数(p)，考虑群(G={1,2,dots,p-1})，群的运算定义为对(p)取模的乘法
(forall ain G, a^{p-1}=1(mod p))
考虑(nin N^{+})，考虑群(G={1leq xleq n~|~gcd(x,n)=1}),群的运算定义为对(n)取模的乘法
(|G|=phi(n))
(forall ain G, a^{phi(n)}=1 (mod n))
例题
(a,bin G)，(o(a)=m)，(o(b)=n)，(ab=ba)
1.证明：若((m,n)=1)，则存在(gin G),s.t. (o(g)=mn)
2.证明：存在(gin G),s.t. (o(g)=lcm(m,n))
证明：
- (g=ab)，假设(o(ab)=k)， 由于((ab)^{mn}=e)，则(kleq mn)
((ab)^{k}=e)，那么(a^{nk}=(ab)^{nk}=e), (m|nk)
同理，(n|mk)
(m|k, n|k)， (mn|k)
综上(k=mn)
- (m=t_1^{p_1}t_2^{p_2}dots t_s^{p_s})
(n=t_1^{q_1}t_2^{q_2}dots t_s^{q_s})
通过交换各个(a_i)的顺序，总能存在(0leq l leq s)，s.t.
(forall ileq l), (p_ileq q_i)
(forall i > l), (p_igeq q_i)
令(c=a^{u},~u=t_1^{p_1}t_2^{p_2}dots t_l^{p_l})
令(d=b^{v},~v=t_{l+1}^{q_{l+1}}t_{l+2}^{q_{l+2}}dots t_s^{q_s})
(o(cd)=lcm(m,n))
由于(o(c)=m/u=t_{l+1}^{p_{l+1}}t_{l+2}^{p_{l+2}}dots t_s^{p_s})
(o(d)=n/v=t_1^{q_1}t_2^{q_2}dots t_l^{q_l})
那么(gcd(o(c),o(d))=1)，又(cd=dc)，由第一小问，(o(cd)=o(c)o(d)=lcm(c,d))
循环群
如果(G=<a>)，称(G)是循环群
举例：对7取余的乘法下，{1,2,3,4,5,6}是循环群
对(k)取余的加法下，({0,1,dots,k-1})是循环群
若(G=<a>)是有限循环群，则(o(a)=|G|)
令(k=o(a))，则(a^k=e)，那么(a^{k+i}=a^i)
考虑({a^1,a^2,dots,a^{k}})，这当中的数两两不同
反证：设(1leq xleq yleq k)，(a^x=a^y),那么(a^{y-x}=e)，矛盾
令(m)是最小的正整数，使得(forall gin G, g^{m}=e)
交换群(G)是循环群，当且仅当(m=|G|)
若(G=<a>)是循环群，则(o(a)=|G|)，所以(mgeq |G|)
又由于(forall gin G), (g^{|G|}=e)，所以(m=|G|)
若(m=|G|)
如果(exists ain G),s.t. (o(a)=|G|)，那么(G=<a>)
否则，(forall gin G), (o(g)<|G|)
设周期最大的元素是(a)，(o(a)=t)
那么(forall gin G), 由刚才的例题，可知(o(g)|t)
那么(t)满足(forall gin G, g^{t}=e)，
由于(m)是最小的正整数，使得(forall gin G, g^{m}=e)，故(mleq t)，矛盾，因此这种情况不会出现
原根
半群：满足封闭性和结合律
交换群：满足交换律的群
环：((R,+,cdot))其中((R,+))是交换群，((R,cdot))是半群
举例子：(Z), (R[x])
域：((F,+,cdot))其中((F,+))是交换群，((Fsetminus{0},cdot))是交换群
(Q,R,C)
代数基本定理：在域(F)中，(n)次非零多项式(f(x))至多有(n)个根
任意一个域的乘法群的有限子群(G)一定是循环群
令(m)是最小的正整数，使得(forall gin G, g^{m}=e)
首先(forall gin G, g^{|G|}=e)，(mleq |G|)
考虑多项式(x^m-e)，(G)中元素都是这个多项式的根，由代数基本定理，(|G|leq m)
因此(m=|G|)
由循环群性质，(G)是循环群。
考虑质数(p)，在对(p)取模的意义下进行加法和乘法，那么({0,1,2,dots,p-1})是一个域
乘法群({1,2,dots,p-1})是循环群
定义：这个循环群的生成元叫做原根
对于原根(a)，(forall 1leq ileq p-1)， (exists x>0), (a^x=i)
一个循环群(G)，设(p-1=|G|)，假设其中(p)是质数
设(a)是生成元
(G={a,a^2,a^3,dots,a^{p-1}})
那么其中(a^{p-1}=e)
如果(g)是原根，当且仅当(o(g)=p-1)
设(g=a^t)，那么(o(g))是最小的(s)使得(p-1~|~st)
(o(g)=p-1)当且仅当(t)与(p-1)互质
因为(st)是(p-1)的倍数，也是(t)的倍数，所以是(t)和(p-1)的公倍数。
若(t)与(p-1)互质，(t)和(p-1)的公倍数最小是(t(p-1))。由于(st)是(t)和(p-1)的公倍数，因此(sgeq p-1)。那么(s=p-1)
若(t)与(p-1)不互质，设它们的最大公约数是(d)，则(d>1)。取(s=(p-1)/d)，则(st=(p-1)t/d=(p-1)(t/d))
欧拉函数：(phi(n))定义为(1)到(n)中与(n)互质的数的数量
那么(|G|)中原根的数量就是(phi(p-1))
由于(phi(p-1))较大，因此寻找原根时，暴力即可，枚举(2,3,dots)，每当枚举到一个数，判断是不是原根。
判断(a)是否是原根是，只需判断是否存在比(p-1)小的数(x)，使得(a^x=1)
枚举(p-1)的所有质因子(d)，判断(a^{frac{p-1}{d}})是否是1
如果都不是，那么(a)就是原根
假设(o(a)=k)，假设(k<p-1)，那么(k|p-1)
由于(a^{gcd(k,p-1)}=1)，所以(k | p-1)
令(t=frac{p-1}{k})，那么(t>1)
令(d)是(t)中任意一个质因子，(frac{p-1}{t}|frac{p-1}{d})，那么(a^{frac{p-1}{d}}=1)
因此只需枚举(p-1)的所有质因子(d)，判断(a^{frac{p-1}{d}})是否是1
十九、离散对数
(G)的原根是(a)，由于(forall gin G)，(exists x, a^x=g)，那么(x=log_{a}{g})
令$q=lceil sqrt{p} ceil $
求出(S={a^0, a^1, dots, a^q})
求出(T={a^0,a^q,a^{2q},dots, a^{q^2}})
任意一个(a^x=g)，因为(x=kq+l, 0leq k,lleq q)，
那么(g=a^{kq} a^{l})
可以写成(g=st,sin S,tin T)
枚举(sin S)，那么需要的(t)就是(s^{-1}g)。对(T)建哈希表（或对(T)排序二分），查找(s^{-1}g)在(T)中是否存在。
这样可以(O(q))的时间复杂度求出(g=st)的形式，进而求出(x=log_{a}{g})
欢迎指正评论O(∩_∩)O~~