NumberTheory
快速幂
模数在 $int$ 范围
1
2
3
4
5
6
7
8
9ll qPow(ll a, ll b, ll c) { //求(a^b) % c
ll ret = 1;
while (b) {
if (b & 0x1) ret = ret * a % c;
a = a * a % c;
b >>= 1;
}
return ret;
}模数超出 $int$ 范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22ll qMulti(ll x,ll y,ll n){ //求(x*y)%n
ll ret=0,tmp=x%n;
while(y) {
if(y&0x1)if((ret+=tmp)>n)ret-=n;
if((tmp<<=1)>n)tmp-=n;
y>>=1;
}
return ret;
}
//O(1)快速乘
ll qMulti(ll x,ll y,ll mod){
return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;
}
ll qPow(ll a,ll b,ll c){ //求(a^b) % c ，c超出int范围
ll ret=1;
while(b) {
if(b&0x1)ret=qMulti(ret,a,c);
a=qMulti(a,a,c);
b>>=1;
}
return ret;
}$\mathcal{O}(1)$ 快速幂
1
2
3
4
5
6int step;
ll pre1[N];//pre1[i]表示a^{i*step}
ll pre2[N];//pre2[i]表示a^{i}
ll qPow(ll a,ll b,ll c){ //求(a^b) % c
return pre1[c/step]*pre2[c%step]%c;
}
欧几里得算法
gcd
1 | ll gcd(ll x,ll y){ |
exgcd
1 | ll exgcd(ll a, ll b, ll &x, ll &y){ //求解ax+by=gcd(a,b),返回gcd(a,b) |
裴蜀定理
$ax+by=c$ 有解的充要条件为 $gcd(a,b) | c$
推广: $a_1x_1+a_2x_2+\cdots+a_nx_n=c$ 有解的充要条件为 $gcd(a_1,a_2,\cdots,a_n) | c$
类欧问题
素数和因子
打表
1 | bool notP[N]; |
区间素数
1 | memset(visab,0,sizeof(visab)); |
唯一分解定理
1 | pair<ll,int> factor[50]; |
n 的因子数
分解 n，$\large n=p_1^{a_1}*p_2^{a_2}\cdots p_m^{a_m}$，n 的因子和为
n 的因子和
分解 n，$\large n=p_1^{a_1}*p_2^{a_2}\cdots p_m^{a_m}$，n 的因子和为
1-n的因子数
$\Large\sum\limits_{i=1}^n\lfloor\frac n i\rfloor$
n=12
| $\large\lfloor\frac n i\rfloor$ | [l,r] |
|---|---|
| 12 | [1,1] |
| 6 | [2,2] |
| 4 | [3,3] |
| 3 | [4,4] |
| 2 | [5,6] |
| 1 | [7,12] |
每个 $l$ 等于上一个 $r+1$，$r=n/(n/l)$
1 | //solution1 |
1-n的因子之和
统计 1-n 每个数取的次数$\Large\frac n i$，即$\Large\sum\limits_{i=1}^n\lfloor\frac n i\rfloor*i$
1 | ll res = 0; |
费马小定理
威尔逊定理
RSA
两个大素数密钥 $p,q$ ，令 $n=p\times q$ ，随机取加密密钥 $e$ ，使得 $gcd(e,(p-1)(q-1))=1$ ，使用 $exgcd$ 计算解密密钥 $d=e^{-1}\mod (p-1)(q-1)$ ， $d$ 与 $n$ 也是互质的。 $e$ 和 $n$ 是公开密钥， $d$ 是私人密钥。
设 $A$ 为明文， $B$ 为密文
积性函数
- $f[1]=1$
- $设n=\prod p_i^{k_i},则f(n)=f(\prod p_i^{k_i})=\prod f(p_i^{l_i})$
- $设n=\prod p_i^{k_i},则f(n)=f(\prod p_i^{k_i})=\prod f(p_i)^{k_i}$ 若满足这一项称为完全积性函数。
欧拉函数
$1\sim n$中与 n 互质的个数(包括 1 )
积性
$prime[i]\le x<prime[i+1]$，必定有$\phi(x)\le prime[i]$
欧拉定理
扩展欧拉定理
$1\sim n$中与 n 互质的数的和为$\large \frac {n*\phi(n)} 2+\epsilon(n)$
设 gcd(n,p)=1，由更相减损术得 gcd(n-p,p)=1，且一定有p≠n-p，故 1~n 中与 n 互质的数可以由此两两配对，而每一对的和都为 n，所以总和为 n*φ(n)/2
求欧拉函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26int euler(int n){
int ans=1;
for (int i=0; i<prime.size()&&prime[i]*prime[i]<=n&&n!=1; i++) {
int e=0;
while (n%prime[i]==0&&n!=1) {
e++;
n/=prime[i];
}
if (e) ans*=pow(prime[i], e-1)*(prime[i]-1);
}
if (n>1) ans*=(n-1);
return ans;
}
O(sqrt(n))
int euler(int n){
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}欧拉函数打表
直接打表
1
2
3
4
5
6for(i=1; i<=maxn; i++) p[i]=i;
for(i=2; i<=maxn; i+=1)
if(p[i]==i){
for(j=i; j<=maxn; j+=i)
p[j]=p[j]/i*(i-1);
}利用线筛打表O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18bool notPrime[N+1];
int prime[N+1],num_prime=0,phi[N];
void get_prime(){
notPrime[1]=1;
for(int i=2;i<=N;i++){
if(!notPrime[i]) {
prime[num_prime++]=i;
phi[i]=i-1;
}
for(int j=0;j<num_prime&&(ll)i*prime[j]<=N;j++){
notPrime[i*prime[j]] = 1;
if(i%prime[j] == 0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
莫比乌斯函数
打表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18bool notPrime[N+1];
int prime[N+1],num_prime=0,miu[N];
void get_prime(){
notPrime[1]=1;
for(int i=2;i<=N;i++){
if(!notPrime[i]) {
prime[num_prime++]=i;
miu[i]=-1;
}
for(int j=0;j<num_prime&&(ll)i*prime[j]<=N;j++){
notPrime[i*prime[j]] = 1;
if(i%prime[j] == 0) {
miu[i*prime[j]]=0;
break;
}else miu[i*prime[j]]=miu[i]*(-1);
}
}
}
除数函数
一些完全积性函数
常函数
单位函数
幂函数
狄利克雷卷积单位函数
卷积
乘积函数
Dirichlet卷积函数
一些卷积
莫比乌斯反演
取模
除法取模
b和m不互质
$\frac a b \%m =\frac{a \% (bm)}b$
证:
设$\frac a b \%m=r$
$\frac a b =km+r$
$a=kbm+br$
$br=a-kbm$
$r=\frac{a \% (b*m)}b$
逆元( inv )
$\frac a b \%m$时，因 $b$ 可能会过大，会出现爆精度的情况，所以需变除法为乘法，设 $c$ 是 $b$ 的逆元，则有 $b*c≡1(mod m)$，即 $\frac a b$ 的模等于 $a\times inv(b)$ 的模；
$m$ 为素数，根据费马小定理 $c=b^{m-2}(\mod m)$ ;
$b*c≡1(\mod m)$ 使用扩展欧几里得算法
逆元打表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//求1,2,...,N关于mod的逆元（mod为质数）
ll inv[N];
inv[1] = 1;
for (int i = 2; i < N; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
/*证明 : i* inv[i] = inv[mod % i] * ((i - 1) * mod + mod - mod / i * i) % mod;
i* inv[i] = inv[mod % i] * ((i - 1) * mod + mod % i) % mod;
i* inv[i] = (inv[mod % i] * (i - 1) * mod + 1) % mod;
i* inv[i] = 1 % mod;*/
//求N!关于mod的逆元（mod为质数）
ll inv[N];
inv[N-1] = qPow(fac[N-1], mod - 2, mod);
for (int i = N - 2; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod;
/*证明 : inv[i + 1] * (i + 1) != 1 % mod;
inv[i + 1] * (i + 1) * i != 1 % mod;*/
组合数取模
n,m 1e5 预处理出逆元和阶乘
1
2
3
4
5
6
7
8
9
10
11ll fac[N],inv[N];
ll C(ll a,ll b){
if(b>a)return 0;
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void init(){//快速计算阶乘的逆元
fac[0]=fac[1]=1;
for(int i=2;i<N;i++)fac[i]=fac[i-1]*i%mod;
inv[N-1] = qPow(fac[N-1], mod - 2, mod);
for (int i = N - 2; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mod;
}n 1e9 , m 1e5
1
2for(int i=1;i<=m;i++)
ans=ans*(n-i+1)%mod*qPow(i,mod-2,mod)%mod;n,m 1e18 , mod 1e5,素数 卢卡斯定理(Lucas)
1
2
3
4
5
6ll Lucas(ll n, ll m){
if(m==0) return C(n, m);
return C(n % mod, m % mod) * Lucas(n / mod, m / mod)%mod;
}
/*表达式：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p。（可以递归）
递归方程：(C(n%p, m%p)*Lucas(n/p, m/p))%p。（递归出口为m==0，return 1）*/exLucas
求解 $C_n^m \mod p$ ， $p$ 不是素数
分解 $\large p=\prod p_i^{k_i}$ ，分别求 $C_n^m\mod p_i^{k_i}$ ，使用中国剩余定理合并
求解 $C_n^m\mod p_i^{k_i}$
易证 $k1-k2-k3\ge0$
求解 $f(n)=\large\frac {n!}{p^a}\mod p^k$ ，分三部分
- $1\sim n$ 中拥有 $p$ 因子的数的贡献：$f(\lfloor\frac n p\rfloor)$
- $\Large\prod\limits_{i=1,(i,p)=1}^{p^k}i^{\lfloor\frac n {p^k}\rfloor}$
- $\Large\prod\limits_{i=1,(i,p)=1}^{n\mod p^k}i$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81ll exgcd(ll a, ll b, ll &x, ll &y){ //求解ax+by=gcd(a,b),返回gcd(a,b)
if(b==0){
x = 1;
y = 0;
return a;
}
ll r = exgcd(b, a%b, y, x);
y -= a/b*x; //这里已经是递归，回溯的过程了，x,y已经颠倒了
return r;
}
ll Chinese_Remainder(ll a[],ll m[],int len){//中国剩余定理 a存放余数 m存放两两互质的数
ll M=1,ret=0;
for(int i = 0; i < len; i++) M *= m[i];
for(int i = 0; i < len; i++){
ll Mi = M/m[i],x,y;
exgcd(m[i],Mi,x,y);
ret = (ret+y*Mi*a[i])%M;
}
return (M+ret%M)%M;
}
ll qPow(ll a, ll b, ll c) { //求(a^b) % c
ll ret = 1;
while (b) {
if (b & 0x1) ret = ret * a % c;
a = a * a % c;
b >>= 1;
}
return ret;
}
ll pre[N],cnt;
ll fac(ll n,ll pk,ll p){
if(n<p)return pre[n];
cnt+=n/pk;
return pre[n%pk]*fac(n/p,pk,p)%pk;
}
ll vp(ll n,ll p){
ll ans=0;
while(n){
ans+=n/p;
n/=p;
}
return ans;
}
ll C(ll n,ll m,ll pk,ll p){
pre[0]=1;
for(int i=1;i<=pk;i++){
pre[i]=pre[i-1];
if(i%p)pre[i]=pre[i-1]*i%pk;
}
cnt=0;
ll ans=fac(n,pk,p)*qPow(pre[pk],cnt,pk)%pk*qPow(p,vp(n,p)-vp(m,p)-vp(n-m,p),pk)%pk;
ll x,y;
cnt=0;
exgcd(fac(m,pk,p)*qPow(pre[pk],cnt,pk)%pk,pk,x,y);
ans=ans*x%pk;
cnt=0;
exgcd(fac(n-m,pk,p)*qPow(pre[pk],cnt,pk)%pk,pk,x,y);
ans=ans*x%pk;
return ans;
}
ll exLucas(ll n,ll m,ll p){
ll a[100],b[100];
int sq=sqrt(p+0.1);
int tot=0;
for(int i=2;i<=sq&&p>1;i++){
int pk=1;
while(p%i==0){
pk*=i;
p/=i;
}
if(pk>1){
a[tot]=C(n,m,pk,i);
b[tot++]=pk;
}
}
if(p>1){
a[tot]=C(n,m,p,p);
b[tot++]=p;
}
return Chinese_Remainder(a,b,tot);
}
$n!$ 中 $p$ (素数) 的幂次
库默尔定理
设 $m,n(\ge0)$，$p$ 为素数，则 $v_p(C_{m+n}^m)$ 等于在 $p$ 进制下 $m+n$ 时进位次数。
连分数
记为
佩尔方程
$x^2-dy^2=1$
- 定理1: 对于正整数 p,q ,如果有则 $\frac p q$ 必为 a 的一个渐进值
1 | //1 |
中国剩余定理
互质
假设整数$m_1,m_2,\cdots,m_n$两两互质，则对任意的整数$a_1,a_2,\cdots,a_n$ 方程组$(S)$有解
设
通解形式为
1
2
3
4
5
6
7
8
9
10ll Chinese_Remainder(ll a[],ll m[],int len){//中国剩余定理 a存放余数 m存放两两互质的数
ll M=1,ret=0;
for(int i = 0; i < len; i++) M *= m[i];
for(int i = 0; i < len; i++){
ll Mi = M/m[i],x,y;
exgcd(m[i],Mi,x,y);
ret = (ret+y*Mi*a[i])%M;
}
return (M+ret%M)%M;
}非互质
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/*采用两两合并的思想
x=a1+m1*x1
x=a2+m2*x2
得到
a1+m1*x1 = a2+m2*x2 → m1*x1+m2*x2 = a2-a1
再通过扩展欧几里得算法解出x1的最小正整数解，代入
x=a1+m1*x1
得到x后合并为一个方程的结果为
y ≡ x(mod lcm(m1,m2))
*/
pair<ll, ll> linear(ll B[], ll M[], ll n){//求解 x = B[i] (mod M[i]),总共n个线性方程组
ll x = 0, m = 1;
for(int i = 0; i < n; i ++) {
ll a = m, b = B[i] - x, d = gcd(M[i], a);
if(b % d != 0) return pair<ll, ll>(-1, -1);//答案不存在，返回-1
ll q ,w;
exgcd(a/d, M[i]/d, q, w);
ll t = b/d * q%(M[i]/d);
x = x + m*t;
m *= M[i]/d;
}
x = (x % m + m ) % m;
return pair<ll, ll>(x, m);//返回的x就是答案，m是最后的lcm值
}
整数拆分
将n划分成若干正整数(可相同)之和的划分数。
dp
$dp[n][m]= dp[n][m-1]+ dp[n-m][m]$, $dp[n][m]$表示整数 n 的划分中，每个数不大于 m 的划分数。 划分分为两种情况:
a.划分中每个数都小于 m，相当于每个数不大于 m - 1, 故划分数为$dp[n][m-1]$
b.划分中有一个数为 m. 那就在 n中减去 m ,剩下的就相当于把 n-m 进行划分， 故划分数为 $dp[n-m][m]$;
dp
$dp[n][k]= dp[n-k][k]+ dp[n-1][k-1]$ ,$dp[n][k]$表示将n划分成k个正整数之和的划分数，划分分为两种情况:
a.不含 1 的分法，为保证每份都 >= 2，可以先拿出 k 个 1 分到每一份，然后再把剩下的 n-k 分成 k 份即可，分法有: $dp[n-k][k]$
b.至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩下的 n- 1 再分成 k- 1 份即可，分法有：$dp[n-1][k-1]$
五边形数
其中 $n-\frac 1 2k(3k-1)>=0 , n-\frac 1 2k(3k+1)>=0$
将n划分成若干正整数(不同)之和的划分数
O(n^2)
$dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]$,$dp[n][m]$表示整数 n 的划分中，每个数不大于m且两两不同的划分数。 划分分为两种情况：
a.划分中每个数都小于m,相当于每个数不大于 m-1,划分数为 $dp[n][m-1]$.
b.划分中有一个数为 m.在n中减去m,剩下相当对n-m进行划分,并且每一个数不大于m-1，故划分数为 $dp[n-m][m-1]$
O(n^1.5)
$dp[i][j]$代表i个数相加等于j ,由于有不同的数最多不超过O(sqrt(n))算法个，则可以优化 $dp[i][j] = dp[i-1][j-i] + dp[i][j-i]$ ,这个递推方程的转移含义是i-1个数每个数都加1,最后再添上一个1，就从$dp[i-1][j-i]$转到$dp[i][j]$,还有就是i个数每个数都加1，就从$dp[i][j-i]$转到$dp[i][j]$
将n划分成若干奇正整数之和的划分数.
法一
$g[i][j]$: 将i划分为j个偶数
$f[i][j]$: 将i划分为j个奇数
$g[i][j] = f[i - j][j]$;
$f[i][j] = f[i - 1][j - 1] + g[i - j][j]$;
法二
奇数和$dp[i][j]$为划分最大的奇数不超过j的数，$dp[i][j]=dp[i-n(j)][j]+dp[i][j-2]$,n(j)为不超过j的最大奇数,初始条件，$dp[i][1]=1$,j为偶数时候$dp[i][j]=dp[i][j-1]$;当i==n(j) ,出现$dp[0][j]$，也就是当i为奇数时候，$dp[0][j]=1$;
其他
n的分拆数中最大部分为m的个数=把n分拆成m部分的个数
n的分拆数中每一部分都小于等于m的个数=把n分成m份或更小
n的分拆数中每部分的数两两不同的个数等于全部都是奇数的个数
n的分拆数中每部分的数都相等的个数=n 的因子个数
n的分拆数中每部分都是1或2(或者把n分拆成1或2部分)的个数=floor(n/2+1)
n的分拆数中每部分都是1或2或3(或者把n分拆成1或2或3部分)的个数=(n+3)^2/12
n的分拆数中每部分都>=k的个数为：f[n]-f[n-1]-f[n-2] · · · +f[n-k] (f[n]表示将n划分成若干正整数(可相同)之和的划分数)
约瑟夫环
令$f[1]$表示$n-m+1$个人玩游戏报 k 退出，第 1 个人退出的编号(下标从 0 开始)；
$f[m]$表示 n 个人玩游戏报 k 退出，第 m 个人退出的编号，
注:当 m<<n 的时候，可以用等差数列的性质，加速运算.
高斯消元
整数
1 | const int MAXN = 300; //有 equ 个方程，var 个变元。增广矩阵行数为 equ, 列数为 var+1, 分别为 0 到 var |
实数
1 | //1 |
母函数
可以看出：$x^2$项的系数$a_1a_2+a_1a_3+ · · · +a_{n-1}a_n$中所有的项包括n个元素$a_1,a_2,· · · ,a_n$中取两个组合的全体，同理：$x^3$项系数包含了从n个元素$a_1,a_2,· · · ,a_n$中取3个元素组合的全体，以此类推。
栗子：
整数拆分
由a,b,c,d….组成n
$G(x)=(1+x^a+x^{2a}+x^{3a}+ · · · )(1+x^b+x^{2b}+x^{3b}+ · · · ) · · · =q_0+q_1x+q_2x^2+q_3x^3+ · · · $
$q_i$表示由a,b,c,d….组成 $i$ 的种类
1 | for (int i=0;i<=n;i++){ |
分治FFT
计算 $\large\prod(1+a_ix)$ ，复杂度 $\mathcal{O}(n*log^2n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69ll qPow(ll a, ll b, ll c) { //求(a^b) % c
ll ret = 1;
while (b) {
if (b & 0x1) ret = ret * a % c;
a = a * a % c;
b >>= 1;
}
return ret;
}
typedef complex <db> cp;
int nn;
cp A[N],omg[M], inv[M];
void init(int a,int b){
nn=1;
while(nn < a + b) nn <<= 1;
for(int i = 0; i < nn; i++){
omg[i] = cp(cos(2 * pi * i / nn), sin(2 * pi * i / nn));
inv[i] = conj(omg[i]);
}
}
void fft(cp *a,cp *type){//type=omg 系数->点值 ; type=inv 点值->系数
int lim = 0;
while((1 << lim) < nn) lim++;
for(int i = 0; i < nn; i++){
int t = 0;
for(int j = 0; j < lim; j++)
if((i >> j) & 1) t |= (1 << (lim - j - 1));
if(i < t) swap(a[i], a[t]); // i < t 的限制使得每对点只被交换一次（否则交换两次相当于没交换）
}
for(int l = 2; l <= nn; l *= 2){
int m = l / 2;
for(cp *p = a; p != a + nn; p += l)
for(int i = 0; i < m; i++){
cp t = type[nn / l * i] * p[i + m];
p[i + m] = p[i] - t;
p[i] += t;
}
}
}
int a[M];
int main(){
int n,trn=1;
in(n);
while(trn<n)trn<<=1;
for0(i,n){
in(a[i]);
}
for0(i,trn){
A[4*i].real(1);
A[4*i+1].real(a[i]);
}
int len=2;
for(int i=4;i<4*trn;i<<=1){
init(len,len);
int nxt_len=2*len-1;
for(int j=0;j<4*trn;j+=2*i){
for(int k=len;k<nn;k++)A[j+k]=A[j+k+i]=cp(0,0);
fft(A+j,omg);fft(A+j+i,omg);
for(int k=0;k<nn;k++)A[j+k]*=A[j+k+i];
fft(A+j,inv);
for(int k=0;k<nxt_len;k++)A[j+k]=cp(ll(A[j+k].real()/nn+0.1)%mod,0);
}
len=nxt_len;
}
for(int i=0;i<=n;i++){
a[i]=A[i].real()+0.1;
out(a[i],0);
}
}
傅立叶变换
DFT
离散傅立叶变换 $O(n^2)$
- 复数相乘的规则：模长相乘，幅角相加。
- 取n个复数，单元根$\large \omega_n=\cos\frac{2\pi}n+i\sin\frac{2\pi}n=e^{i\frac {2\pi}n}$，取$\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1}$
- $\omega_{2n}^{2k}=\omega_{n}^{k}$
- $\omega_{n}^{k+\frac n2}=-\omega_{n}^{k}$
- $\omega_n^0=\omega_n^n=1$
- 设$(y_0,y_1,\cdots,y_{n-1})$为多项式$A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}$的离散傅立叶变换，设多形式$B(x)=y_0+y_1x+\cdots+y_{n-1}x^{n-1}$，取$\omega_n^0,\omega_n^{-1},\omega_n^{-2},\cdots,\omega_n^{-(n-1)}$代入$B(x)$得$(z_0,z_1,\cdots,z_{n-1})$，易证$a_i=\frac {z_i} n$
FFT
快速傅立叶变换，在$O(n log n)$的时间内将一个多项式转换成它的点值表示(或相反)的算法
设$A(x) = a_0 + a_1x + a_2x^2 +…+a_{n-1}x^{n-1}$，将$A(x)$拆分成奇偶两部分：
设：
当$k<\frac n 2$时，
当$>\frac n 2$时，
蝴蝶操作
1 | typedef complex <double> cp; |
NTT
特定模数
将单元根$\omega _n=e^{i\frac {2\pi}n} $变为$g^{\frac {P-1} n}$，需要满足模数 P 是质数且 P−1 是 n (2的次幂) 的倍数。即：
显然对$\omega _n=g^{\frac {P-1} n}$有$\omega_{2n}^{2k}=\omega_{n}^{k}$，而且由于$g^{\frac {P-1} {2n}}\equiv -1 (mod P)$所以$\omega_{n}^{k+\frac n2}=-\omega_{n}^{k}$
1 | int n,r[N]; |
三模数
两个多项式相乘后，每位的答案一定小于1e9*1e9*n，即1e24，所以我们选3个乘积大于1e24的NTT模数，分别做一次，得到每个位上模意义下的答案，再做CRT，先将两个模数意义下的答案合并，得到两个模数，设模数为P1(longlong) ,P2(int), 余数为a1,a2。设答案$ANS=P1\times K+a1=P2\times Q+a2$，那么$K\times P1=P2\times Q+(a2-a1)$，$K\times P1 \% P2=a2-a1$，$a1-a2$为常数，用同余方程的解法即可解出K模P2(int)意义下的值，又有$ANS<P1\times P2$，所以 $K\times P1+a1<P1\times P2$，显然$K<P2$，所以原本答案K的值只能为模P2意义下的值。
1 |
|
MTT
将多项式的每个系数拆成$k\times M+b$的形式，其中 M 为常数,考虑卷积过程：
当$M=\sqrt P$时,这些东西都是 P 的级别，所以FFT 出来的结果都是1e14级别的。所以需要4次 FFT 和3次 IFFT。进一步优化，定义
则会有
于是我们只用DFT这个P(x)，就能得到Q(x)被DFT之后的结果,还可以求得 A，B 的 FFT。这样我们就可以处理出$a=k_1k_2,b=k_1b_2,c=k_2b_1,d=b_1b_2$的值，然后构造M1=a+bi和M2=c+di两个多项式，IDFT回去。则分别取这两个IDFT后的多项式的实部和虚部（第一个的实部为a，虚部为b以此类推），就是IDFT后的a,b,c,d节约2的常数，这样只要做四次DFT即可。
1 |
|
FWT
快速沃尔什变换，利用类似 $FFT$ 的东西解决多项式的位运算卷积
定义：
寻找 $FWT(A\oplus B)=FWT(A)\times FWT(B)$
or
对于长度为 $2^n$ 的多项式，$A_0$ 是前 $2^{n-1}$ 前项，$A_1$ 是后 $2^{n-1}$ 前项
and
对于长度为 $2^n$ 的多项式，$A_0$ 是前 $2^{n-1}$ 前项，$A_1$ 是后 $2^{n-1}$ 前项
xor
对于长度为 $2^n$ 的多项式，$A_0$ 是前 $2^{n-1}$ 前项，$A_1$ 是后 $2^{n-1}$ 前项
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39ll qPow(ll a, ll b, ll c) { //求(a^b) % c
ll ret = 1;
while (b) {
if (b & 0x1) ret = ret * a % c;
a = a * a % c;
b >>= 1;
}
return ret;
}
int n,inv_2;
void init(int maxx){//maxx=max(len_a,len_b)
n=1;
while(n<maxx)n<<=1;
inv_2=qPow(2,mod-2,mod);
}
void FWT_or(int *a,int opt){//type=1 系数->点值 ; type=-1 点值->系数
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;++k)
if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k])%mod;
else a[i+j+k]=(a[i+j+k]+mod-a[j+k])%mod;
}
void FWT_and(int *a,int opt){
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;++k)
if(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%mod;
else a[j+k]=(a[j+k]+mod-a[i+j+k])%mod;
}
void FWT_xor(int *a,int opt){
for(int i=1;i<n;i<<=1)
for(int p=i<<1,j=0;j<n;j+=p)
for(int k=0;k<i;++k){
int X=a[j+k],Y=a[i+j+k];
a[j+k]=(X+Y)%mod;
a[i+j+k]=(X+mod-Y)%mod;
if(opt==-1) a[j+k]=1ll*a[j+k]*inv_2%mod , a[i+j+k]=1ll*a[i+j+k]*inv_2%mod;
}
}
FMT
快速莫比乌斯变化
阶乘最末尾非零
设 $G(n)$ 为除去 $5$ 的倍数的前 $n$ 项乘积的末尾位
$\frac 2 2=6, \frac 4 2=2, \frac 6 2=8, \frac 8 2=4$
$\huge\frac {G(n)} {2^{\lfloor\frac n 5\rfloor\%4}}$有一个长度为20的循环节6,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2,6
1 | //普通版 |
二次剩余
当存在某个 $X$，式子 $X^2 = n (\% p)$ 成立时，称 $n$ 是模 $p$ 的二次剩余
当对任意 $X$ 不成立时，称 $n$ 是模 $p$ 的二次非剩余
定理1: 对于 $x^2 = n (\% p)$ 总共有 $\frac {p-1} 2$ 种 n 能使方程有解(排除n=0)
引理: p为奇素数
定理2: 勒让德符号(Legendre symbol)
二次互反律
设 p,q 是不同的奇素数, 则
广义二次互反律
设 a,b 为正奇数, 则
Cipolla算法
求解 $x^2 = n (\% p)$
当 $\omega=a^2-n$ 不是模 p 的二次剩余 $x=(a+\sqrt {\omega})^{\frac {p+1}2}$证明:
1 | //方案1: |
求解 $x^2 = n (\% p^a)$ , 其中 $gcd(n , p) = 1$, 并且 p 为奇质数
若 r 是 $x^2 = n (\% p)$ 的一个解
二次同余方程模合数
求出 $x_1,x_2,\cdots,x_m$ 再用中国剩余定理求解
阶
定义
设 $m>1 , (a,m)=1$，满足 $a^x\equiv 1(\mod m)$ 的最小的 $x$，称为 $a$ 对 $m$ 的阶，记为 $\delta_m(a)$
定理与推论
- 若 $m>1,(a,m)=1$ 且 $a^n\equiv 1(\mod m),n>0$ ，则 $\delta_m(a) | n$
- $\delta_{m}(a) | \phi(m)$
- 若 $p,q$ 为奇素数，且 $q | (a^p-1)$，则或有 $q | (a-1)$，或有 $q=2kp+1$，其中 $k$ 为某整数
- $2^p−1$ 的任何因子必取 $2kp+1$ 的形式。
- $\large a^{0}, a^{1}, \dots, a^{\delta_m(a)-1} $ 构成模 m 的既约剩余系
- $a^{x} \equiv a^{y}(\bmod m) \Leftrightarrow x \equiv y\left(\bmod \delta_{m}(a)\right)$
- $\Large \delta_{m}\left(a^{d}\right)=\frac{\delta_{m}(a)}{\left(\delta_{m}(a), d\right)}$
求法
分解 $\Large \phi(m)=\prod p_i^{k_i}$ ， 逐渐减小 $k_i$ ，记为 $P$，直到再减一 $[a^P\ne 1(\mod m)]$ 为止
1 | ll qPow(ll a, ll b, ll c) { //求(a^b) % c |
原根
定义
当 $\delta_m(a)=\phi (m)$ 时称为 $a$ 为 $m$ 的原根
定理与推论
- 若 $g$ 是 $m$ 的一个原根，则 $g, g^{2}, \cdots, g^{\phi(m)}$ 各数对模 $m$ 的最小剩余，恰是小于 $m$ 且与 $m$ 互素的 $\phi(m)$ 个正整数的一个排列。
- $m$ 的原根(若存在)的数目为 $\large\phi(\phi(m))$
- $m$ 有原根 $\Longleftrightarrow$ $\large m=1,2,4,p^k,2p^k$ （ $p$ 为奇素数）
- 若 $d|(p−1)$ ,则 $x^d\equiv 1(\mod p)$ 恰有 $d$ 个解
- 若 $p$ 为素数,$d|(p−1)$,则阶为 $d$ 的最小剩余 $(\mod p)$ 的个数为 $\phi(d)$
- 一个数的最小原根为 $O(n^{0.25})$
- 若 $g$ 是 $m$ 的原根，则 $g^d$ 为 $m$ 的原根的充要条件为 $(d,\phi(n))=1$
求法
分解 $\Large \phi(m)=\prod p_i^{k_i}$ ，枚举 $g$ ，直到 $\Large g^{\frac {\phi(m)} {p_i}}\ne 1(\mod m)$
1 | ll qPow(ll a, ll b, ll c) { //求(a^b) % c |
离散对数
定义
设 $g$ 是 $m$ 的一个原根，当 $g^t\equiv k(\mod m)$ 时，$in d_gk\equiv t(\mod \phi(m))$ ，此处的 $ind_gk$ 表示 $k$ 以 $g$ 为底，模 $\phi(m)$ 的离散对数值
定理与推论
- $ind_gab\equiv ind_ga+ind_gb (\mod \phi(m))$
- $ind_ga^n\equiv n\times ind_ga (\mod \phi(m))$
BSGS 算法
$a^x\equiv C(\% m) , gcd(a,m)=1$
$0\le x< \delta_m(a)$, 设 $x=uT-v$ , 则原方程转化为 $\large a^{uT}\equiv Ca^v(a^{-1}存在)$, 我们可以预处理出每一个 $Ca^v$ 对每个 $a^{uT}$ 找一下有没有等于 $Ca^v$
1 | //map |
扩展 BSGS
初始方程为
设 $b’=b,p’=p$，初始化 $v= 1$，每次约分拿出一个 $a$ ，令
如果
$d=1$，则约分过程结束，约分完成。否则的话，如果 $d$ 不能整除
$b’$，说明无法完成约分，$x$ 无解，整个算法结束。
再否则的话，更新
$b’，p’，v$ 为
然后继续循环进行下一轮约分。
其中 $v$ 即为 $a$ 每次约分剩下的没有被约掉的因子的乘积。约分完成后，假设约分了 $cnt$ 次，则程变为
此时
$(a，p’) = 1$，显然我们可用基本的 $BGGS$ 算法求得 $x -cnt$ 的值，算法至此结束。
具体可参考下方的实现理解。
1 | ll exBSGS(ll a, ll b, ll p) { |
全错位排列
其他
康托展开
计算当前排列在所有由小到大全排列中的顺序
$X = A[0] \times (n-1)! + A[1] \times (n-2)! + … + A[n-1] \times 0! $
$A[i]$ 指的是位于位置 $i$ 后面的数小于 $A[i]$ 值的个数,后面乘的就是后面还有多少个数的阶乘
说明 ：这个算出来的数康拖展开值，是在所有排列次序 $- 1$的值，因此 $X+1$ 即为在全排列中的次序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16//返回数组a中当下顺序的康拖映射
int cantor(int *a,int n)
{
int ans=0;
for(int i=0;i<n;i++)
{
int x=0;int c=1,m=1;//c记录后面的阶乘
for(int j=i+1;j<n;j++)
{
if(a[j]<a[i])x++;
m*=c;c++;
}
ans+=x*m;
}
return ans;
}
逆康拖展开
例子 ：
在（1，2，3，4，5) 给出61可以算出起排列组合为34152
具体过程如下：
用 61 / 4! = 2余13，说明 ,说明比首位小的数有2个，所以首位为3。
用 13 / 3! = 2余1，说明 ，说明在第二位之后小于第二位的数有2个，所以第二位为4。
用 1 / 2! = 0余1，说明 ，说明在第三位之后没有小于第三位的数，所以第三位为1。
用 1 / 1! = 1余0，说明 ，说明在第二位之后小于第四位的数有1个，所以第四位为5。
1 | static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘 |
高斯整数
高斯整数是实数和虚数部分都是整数的复数。所有高斯整数组成了一个整域，写作 $Z[i]$, 是个不可以转成有序环的欧几里德域。$Z[i] = \{a+bi | a,b \in \mathbb Z \}$
$Z[i]$ 的单位元是 $1,-1,i,-i$
对 $Z[sqrt(-k)], k \in \{1,2,3,7,11,19,43,67,163\}$ 才满足唯一分解定理
高斯素数
- $a ,b$ 中有一个是 $0$,另一个是形如 $4n+3$ 或 $-(4n+3)$ 的素数
- $a,b$ 均不为 $0$，$a^2+b^2$ 为素数
四平方和定理
每个正整数均可表示为4个整数的平方和
费马平方和定理
奇素数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
如果两个整数都能表示为两个平方数之和，则它们的积也能表示为两个平方数之和。
如果一个能表示为两个平方数之和的整数被另一个能表示为两个平方数之和的素数整除，则它们的商也能表示为两个平方数之和。
如果一个能表示为两个平方数之和的整数被另一个不能表示为两个平方数之和的整数整除，则它们的商也必有一个不能表示为两个平方数之和的因子。
如果 $a$ 和 $b$ 互素，则 $a^2+b^2$ 的所有因子都能表示为两个平方数之和。
阶乘近似
Ｎ以内相邻素数最大间距
$ln N \times (ln N - 2\times ln ln N)+2$
调和级数
快速平方根倒数
$\frac 1 {\sqrt x}$
1 | float fast_inverse_sqrt(float x) { |
N 次剩余
$x^a\equiv b(\% p)$
$p$ 为素数
设 $g$ 为 $P$ 的一原根，记 $k$ 关于 $g$ 的离散对数 $(mod p)$ 为 $ind_dk$，则有
设
$t_1=ind_gb$，则有
$g^{t_1}\equiv b (mod p)$ 。那么 $t_1$ 即与情形2—致，可由 $BSGS$ 算法求出
$t_1$。设
$t_2=ind_gx$，则原式变为
$a\times t_2\equiv t_1 (mod \phi (p))$
其中只有
$t_2$ 是未知的，可由扩展欧几里德求出所有 $t_2$
的值。
又由
$t_2=ind_gx$
知 $g^{t_2}\equiv x (mod p)$ 与情形1 一致，可由快速幂求出所有 $x$ 值。
至此解决 $P$ 为素数时的问题。p为合数
首先将 $p$ 分解素因子为
$p=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$那么我们对每一个 $i$ 属于 $[1,\cdots,k]$，都有
$x^a \equiv b (mod p_i^{e_i})$ 我们可利用上面的知识去解出这里的 $x$，不过由于模数不一定为素数的原因，不能单纯地使用上面 $p$ 为素数的方法去解，关于这个式子的解法是解决整个问题的关键，下面会给出细节，此处暂且认为已经解出 $x$ 的一
组解 $x_{i1},x_{i2},\cdots,x_{it_i}$。那么上面 $k$ 个式子就会有 $k$ 组这样的解，我们从每组里取一个 $x$ 值出来，记为 $\{X_1,X_1,\cdots,X_k\}$，那么如果我们能找到一个 $z$ 满足
那么 $z$ 必为原式的一个解。而要解这个，只需使用 $CRT$ 即可，同时我们需要一个 $dfs$ 来枚举所有 $X$ 可能的组合。
至此解决问题。
大素数判断
1 | /* |
Pollard-Rho 质因数分解
1 | ll factor[100];//质因数分解结果（刚返回时是无序的） |
