ACM模板

it2023-12-21  64

数论

1.康托展开

2.第一类斯特林数

S ( n , m ) S(n,m) S(n,m)记为将 n n n个元素划分为 m m m个圆排列的方案数

递推式: S ( n , m ) = S ( n − 1 , m − 1 ) + ( n − 1 ) ∗ S ( n − 1 , m ) S(n,m) = S(n-1,m-1) + (n - 1) * S(n-1,m) S(n,m)=S(n1,m1)+(n1)S(n1,m) $ ,$ n > m n > m n>m

边界: S ( n , 0 ) = 0 S(n,0) = 0 S(n,0)=0 S ( n , n ) = 1 S(n,n) = 1 S(n,n)=1

3.逆元线性求组合数

void make_inv() { fac[0] = inv[0] = inv[1] = 1; for (int i = 2; i < N; ++i) { inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; } for (int i = 1; i < N; ++i) { fac[i] = fac[i-1] * i % MOD; inv[i] = inv[i] * inv[i - 1] % MOD; } } int C(int n,int m) { if (n < m) return 0; return fac[n] * inv[m] % MOD * inv[n - m] % MOD; }

4.埃氏素数筛法

const int MAX_N = 1e5 + 10; int CNT, prime[MAX_N]; bool vis[MAX_N]; void make_prime() { CNT = 0; for(int i = 2; i < MAX_N; ++i) { if(!vis[i]) { prime[++CNT] = i; for(int j = 2; j * i < MAX_N; ++j) vis[i*j] = true; } } }

5.欧拉线性筛

int prime[30000010], minprime[30000010], phi[30000010]; // 第i个质数,i的最小质因子,i的欧拉函数 int euler(int n) { int c=0,i,j; phi[1]=1; for(i=2; i<=n; i++) { if(!minprime[i])prime[++c]=i,minprime[i]=i,phi[i]=i-1; for(j=1; j<=c&&i*prime[j]<=n; j++) { minprime[i*prime[j]]=prime[j]; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } return c; // 返回n范围内素数个数 }

Miller_Rabin 快速大素数测试

可以测试 2 63 2^{63} 263(甚至更高)以下的数是否为素数(但可能是伪素数)

#define ull unsigned long long const int S = 4; // 测试次数,一般4~8次 ull mulit_mod(ull n, ull a, ull MOD) { a %= MOD, n %= MOD; ull ans = 0; for(; n; n >>= 1, a = (a + a) % MOD) if(n & 1) ans = (ans + a) % MOD; return ans; } ull pow_mod(ull n, ull a, ull MOD) { ull ans = 1; for(; n; n >>= 1, a = mulit_mod(a, a, MOD)) if(n & 1) ans = mulit_mod(ans, a, MOD); return ans; } bool Miller_Rabin(ull n, ull a) { ull d = n-1, s = 0, t; while(!(d&1)) d >>= 1, ++s; t = pow_mod(d, a, n); if(t == 1 || t == -1) return true; for(int i = 0; i < s; ++i) { if(t == n-1) return true; t = mulit_mod(t, t, n); } return false; } bool is_prime(ull n) { if(n < 2) return false; if(n == 2) return true; if((n&1) == 0) return false; srand(time(NULL)); for(int i = 0; i < S; ++i) { ull a = rand() % (n-1) + 1; if(a != 1 && n % a == 0) return false; if(!Miller_Rabin(n, a)) return false; } return true; }
最新回复(0)