数论在OI中还是比较重要的,这些笔记是在课上匆忙记下的,可能不太美观。
一些约定:在这里整数间除法是向下取整;\((a,b)\)代表\(gcd(a,b)\)
小凯的疑惑
\(sol\):构造
\(ax+by = k(a,b >= 0)\) 使其无解
设一组解\(x1 \in [0,b-1] ,y1>=0\)
若\(k>ab-a-b\)
则$y1>(k-a*x1)/b = (ab-a-b-a(b-1))/b $ \(= -1\)
即\(y1>=0\)
故\(k=ab-a-b\)是符合条件的最大值
上帝与集合的正确用法--扩展欧拉定理
https://www.lydsy.com/JudgeOnline/problem.php?id=3884
屠龙勇士--扩展中国剩余定理
用\(f(i)\)表示有序三元组(a,b,c)个数,使得\(a*b*c=i\),求出\(f(1)\)~\(f(n)\)
$sol: i=\prod {p_i}^{c_i} $ $ f(i)=\prod C^{ci+2}_2$ 使用扩展欧拉筛
数论之神
线性推逆元:
? \(inv[fac[i]] = inv[fac[i+1]]*(i+1)\)
设\(p=i*k+r\)
\(i*k+r \equiv 0 \mod p\)
\(i*k \equiv -r \mod p\)
\(r^{-1}*k \equiv -i^{-1} \mod p\)
\(i^{-1} \equiv -p/i*inv[p \% i]\) \(\mod p\)
中国剩余定理
ExCRT(增量法):若m不互质
$x \equiv a \mod b -> x=kb+a $
\(x \equiv c \mod d -> kb+a \equiv c \mod d -> kb+pd = c-a\)
条件\((c-a)|gcd(b,d)\)
求解后回代即可
埃式筛
欧拉筛-扩展 (未懂)
Miller-Rabin(未懂)
费马小定理&&二次剩余
Pollard-Rho(未懂)
生日攻击
类欧几里得算法(未懂)
? https://www.cnblogs.com/LLppdd/p/8428349.html
BSGS&&ExBSGS
\(扩展欧几里得Exgcd:\)
\(a \mod b = a-a/b*b\)
\(ua+vb = gcd(a,b)\)
\(u‘b+v‘(a mod b) = gcd(a,b)\)
\(u‘b+v‘(a-a/b*b) = gcd(a,b)\)
\(v‘a+(u‘-a/b*v‘)*b = gcd(a,b)\)
通解:$x_0=x+t*b/(a,b) $ \(y_0=y-t*a/(a,b)\)
\((k,m)=d\) \(且\) \(ka \equiv kb \mod m -> a \equiv b \mod m/d\)
\(Prove: ka \equiv kb \mod m -> m|(ka-kb) -> m|k(a-b) -> (m/d)|(a-b)\)
所有\(0<n<=m,(n,m)=1\)的n构成了模m的简化剩余系,简称缩系
记这样n的个数为$ \phi(m)$
计算公式:\(\phi(p)= \prod \phi(p_i^{c_i}) = \prod (p^c_i * (1-1/p_i)) = n* \prod (1-1/p_i)\)
欧拉定理 如果\((a,m)=1,a^{phi(m)} \equiv 1 \mod m\)
$Prove: $设x取遍m的缩系,则ax取遍m的缩系
$ \prod x = \prod ax \mod m$
$\prod x = \prod x *a^{ \phi(m)} \mod m $ //这样的a有phi(m)个
由于\((x,m)=1\),保证$\prod x $存在模m意义下的逆元
所以 \(a^{ \phi(m)} \equiv 1 \mod m\)
费马小定理 如果\((a,m)=1\),且m是个质数 $a^{m-1} \equiv 1 \mod m $
扩展欧拉定理 如果$(a,m)!=1 $ 则 \(a^b \equiv a^{min(b,b \% \phi(m)+\phi(m))} \mod m\)
阶
如果(a,m)那么最小的正整数使得\(a^{x} \equiv 1 \mod m\),x称为a模m的阶
性质:\(x|\phi(m)\)
Prove:
原根
如果g在模m的阶是\(\phi(m)\),那么称g是模m的原根
积性函数
欧拉函数,莫比乌斯函数,除数函数
狄利克雷卷积
满足交换律结合律分配律,可用倍增
\((f*g)(n) = \sum_{d|n} f(d)*g(n/d)\)
如果f,g是积性函数,f*g也是积性函数
\(f*e=f\) 单位元:e \(e(1)=1\),其他\(e(i)=0\);
莫比乌斯函数
\(e(n)=\sum_{d|n}mu(d)\)
Prove:转化为二项式系数后转化
? 性质: \(e(n)=mu(n)*1\)
莫比乌斯反演
若\(f(n)=\sum_{d|n} g(d)\)
则\(g(n)=\sum_{d|n} mu(d) f(n/d)\)
\(Prove:\)
\(f = g*1\) \(mu*1 = e\)
\(f*u = g*1*mu\)
\(f*u = g*e\)
$g=f*u $ -> \(g(n)= \sum_{d|n} mu(d) f(n/d)\)
原文:https://www.cnblogs.com/Rye-Catcher/p/9383319.html