整除
对于两个整数 (a , b) ，若 (exists kin Z) 使 (ak=b) 则称 (a) 整除 (b) ，记做 (a|b)
快速幂
好像没什么好讲的...讲下证明
对于求 (x^y) ，将 (y) 表示为二进制，如： (105_{(10)}=1101001_{(2)})
所以 (x^y=x^{2^6+2^5+2^3+2^0}=x^{2^6}x^{2^5}x^{2^3}x^{2^0})
| x | ans |
|---|---|
| (x) | (x^{2^0}) |
| (x^2) | (x^{2^0}) |
| (x^4) | (x^{2^0}) |
| (x^8) | (x^{2^3}x^{2^0}) |
| (x^{16}) | (x^{2^3}x^{2^0}) |
| (x^{32}) | (x^{2^5}x^{2^3}x^{2^0}) |
| (x^{32}) | (x^{2^6}x^{2^5}x^{2^3}x^{2^0}) |
(mathcal{Code}:)
#define int long long
int ksm(int a,int b,int mod){
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans%mod;
}
例题：P1226 快速幂
gcd
对于两个数 (a) , (b) 的最大公约数
裴蜀定理
对于任意 (x , y) 都 (exists a,b) 满足 (ax+by=gcd(x,y))
证明：就算百度百科你们都能看懂
应用
用来做题
可以用来证明奇奇怪怪的东西和推式子
信息上对于这东西常见的套路是枚举(gcd)
如：给你T组数据,求 (displaystylesum_{i=1}^n sum_{j=1}^m gcd(i,j))
其中有一步是标准的枚举 (gcd)
(displaystyle{egin{aligned}&sum_{i=1}^n sum_{j=1}^m gcd(i,j)\=&sum_{i=1}^n sum_{j=1}^m sum_{d|i,j}d[gcd(frac id,frac jd)==1]end{aligned}})
(mathcal{Code}:)
//__gcd(x,y)
//emmming...
inline void gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
例题（注意卡常）：UVA11426 GCD - Extreme (II)
exgcd
定义
一种算法
首先根据裴蜀定理，对于等式 (ax+by=gcd(a,b)) 一定存在整数解
(EXgcd) 就是求该等式的一组特解
求法
推柿子~
(left{ egin{array}{lrc} ax+by=gcd(a,b)\ bx'+(a\%b)y'=gcd(b,a\%b)\a\%b=a-b*lfloorfrac ab floor\gcd(a,b)=gcd(b,a\%b) end{array} ight.Rightarrowleft{egin{array}{lrc} x=y'\y=x'-y'lfloorfrac ab floor end{array} ight.)
之后令(g=gcd(a,b))
则 (lcm(a,b)=a*b/g)
又 (ax+lcm(a,b)+by-lcm(a,b)=c)
故有 (a(x+b/g)+b(y-a/g)=c)
由此可得，(x) 加上或减去任意倍数的 (b/gcd(a,b)) 后均有对应的y的解
令 (t=b/g)， ((x\%t+t)\%t) 就是x的最小非负解
(mathcal{Code:})
inline void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
(lcm)
这个真没什么好说的
(lcm) 这东西在数论推柿子里因没有什么性质而遭到嫌弃
通常把 (lcm) 转化为 (gcd) 来做： (lcm(i,j)=frac {i*j}{gcd(i,j)})
注意，这一条性质只在两个数时才成立，其他情况不一定，比如
(frac {1*2*3*4*5}{gcd(1,2,3,4,5)} = 1*2*3*4*5 eq lcm(1,2,3,4,5))
例题： P1891 疯狂LCM
同余
对于两整数 (a , b) 若 (amod p=bmod p) 则称 (a) 与 (b) 在模 (p) 意义下同余
用符号表示则为 (a equiv b pmod p)
性质
对称性：(aequiv bpmod pRightarrow bequiv apmod p)
可乘性：若 (aequiv bpmod p,cequiv dpmod p) ，则 (acequiv bdpmod p)
应用
对于信息比较基本，没有什么应用，主要用在定理的证明和表达中
对于同余式 (ax equiv b pmod p) ,可以转化为 (ax+kp=b) 就可以应用 exgcd 求了
特殊的，对于同余式 (a equiv 1 pmod p) 的一个解是 (a) 在模 (p) 意义下的逆元
例题： P1082 同余方程
逆元
对于整数(a，p)，(exists a^{-1}) 满足 (a*a^{-1} equiv 1(mod p)) 则称 (a^{-1}) 是 (a) 在模 (p) 意义下的逆元
主要用于除法取模问题
因为除法不对模运算封闭，所以逆元应运而生
求逆元主要用两种方法，一是费马小定理，二是 exgcd，三是线性
只列出线性的代码
(mathcal{Code}:)
inv[1]=1;
for(int i=2;i<=n;i++)
inv[i]=((p-p/i)*inv[p%i])%p;
埃拉托色尼筛法
复杂度 $O(n loglogn) $
所以建议用欧拉筛 (O(n))
在此讲一下原理
对于一个数 (a) , 则 (k*a (k in N^*)) 一定不会在之后的循环中进入素数表，所以给他们打上标记
因为埃氏筛会对一些数重复筛，所以复杂度就不如欧拉筛优
(mathcal{Code}:)
inline void pri(){
for(int i=2;i<=n;i++){
if(!ispri[i]) prime[++cnt]=i;
for(int j=1;j<=cnt;j++){
ispri[i*prime[j]]=1;
// if(!(i%prime[j])) break;
}
}
}
例题：P3383 线性筛素数(这题好像 (Theta (n^2)) 都能过)
杜教筛
对于一个积性函数 (f)，我们要求 (sum_{i=1}^n f(i))
(mathcal{Ans})：
令 (S(n)=sum_{i=1}^n f(i))，(h=g*f) (h，g为任意积性函数)
则 (displaystylesum_{i=1}^{n}(f*g)(i))
(displaystyle{egin{aligned} &= sumlimits_{i=1}^{n} sum limits _{d|i} g(d)f(frac{i}{d}) \ &= sum limits _{d=1}^{n} g(d)sumlimits _{i=1}^{lfloor frac{n}{d}
floor } f(i) \ &= sum limits _{d=1}^{n} g(d) S(lfloor frac{n}{d}
floor) end{aligned}})
又 (g(1)S(n)=sum_{d=1}^ng(d)S(lfloorfrac nd floor)-sum_{d=2}^ng(d)S(lfloorfrac nd floor))
则(g(1)S(n)=sumlimits_{i=1}^{n}(f*g)(i)-sum_{d=2}^ng(d)S(lfloorfrac nd floor))
进行预处理&数论分块即可
例题：P4213 杜教筛
Lagrange 插值
孙子定理
若(m_1,m_2,cdots,m_n)是两两互质的正整数，(M=prod_{i=1}^n{m_i})，(M_i=M/m_i) , (t_i)是线性同余方程(M_it_iequiv 1 (mod m_i))的一个解
对于任意的n个整数(a_1,a_2,cdots,a_n)，则同余方程组： (egin{cases}x≡a_1(mod m_1)\x≡a_2(mod m_2)\ cdots cdots\x≡a_n(mod m_n)\end{cases}) 有整数解(x=displaystylesum_{i=1}^n M_it_i a_i).并且在(mod M) 意义下有唯一解。
证明
因为(M_i=M/m_i) 是除(m_i)之外所有模数的倍数，所以(forall k ot=i , M_it_ia_iequiv 0 (mod m_k))
又因为(M_it_ia_iequiv a_i (mod m_i))
所以 (x=displaystylesum_{i=1}^n M_it_i a_i)
结论
CRT给出了模数两两互质的线性同余方程组的一个特解。方程组的通解可以表示为 (x+kM (kinmathbb Z))。有些题目要求我们求出最小的非负整数解，只需把 (x) 对 (M) 取模，并让x落在 ([1,M)) 内即可。
正文
对于一个多项式 (f(x))，其图像在坐标系内经过 (n) 个点 ((x_i,y_i))
我们考虑对于此多项式的“孙子定理”：
构造 (n) 个多项式 (g_i(n)).对于第 (i) 个多项式，对于(forall k ot= i ，g_i(x_k)=0)，而 (g_i(x_i)=1)，即 (g_i(x_i)*y_i=y_i)
则可得 (g_i(x)=dfrac{(x-x_1)(x-x_2)cdots(x-x_{i-1})(x-x_{i+1})cdots(x-x_n)}{(x_i-x_1)(x_i-x_2)cdots(x_i-x_{i-1})(x_i-x_{i+1})cdots(x_i-x_n)})
所以 (f(x)=displaystylesum_{i=1}^n g_i(x)*y_i)
(mathcal{Code})：
inline int Lagrange(){//求f(k)%998244353
int ans=0;
for(int i=1,res;i<=n;i++){
res=1;
// cout<<i<<":
";
for(int j=1;j<=n;j++){
if(j==i) continue;
res=(res*((x[i]+mod-x[j])%mod))%mod;
}
res=ksm(res,mod-2);
for(int j=1;j<=n;j++){
if(j==i) continue;
res=(res*((k+mod-x[j])%mod))%mod;
}
res=res*y[i]%mod;
ans=(ans+res)%mod;
// cout<<ans<<"
";
}
return ans;
}
例题：P4781 拉格朗日插值
莫比乌斯
积性函数
积性函数指：(forall a, b ∈ mathbb N^+,gcd(a, b) = 1,s.t.f(ab)=f(a)f(b))
Dirichlet卷积
((f*g)(n)=displaystylesum_{d|n}f(d)g(dfrac nd))
性质
- 交换律：(f*g=g*f)
- 结合律：((f*g)*h=f*(g*h))
- 分配律：(f*(g+h)=f*g+f*h)
- 单位元：(f*epsilon=f)
- 若(f,g) 为积性函数，那么 (f*g) 也是积性函数。
莫比乌斯等式
(epsilon(n)=displaystylesum_{d|n}mu(d))
例题
(displaystylesum_{i=1}^nsum_{j=1}^msum_{d|i,j} dfrac{ij}{gcd(frac id,frac jd)})