判断质数
bool isprime (int n){
for (int i = 2;i * i <= n;i ++)
if (n % i == 0)
return 0;
return 1;
}
整数的唯一分解
void factorize(int n){
for (int i = 2;i * i <= n;i ++)
if (n % i == 0){
p[++ k] = i;
while (n % i == 0)
n /= i,w[k] ++;
}
if (n != 1)
p[++ k] = i,w[k] = 1;
}
埃拉托斯特尼筛法
void sieve(int n){
for (int i = 2;i <= n;i ++){
if (!vis[i]){
prime[++ pn] = i;
for (int j = i * i;j <= n;j += i)
vis[j] = 1;
}
}
}
筛法求约数个数,约数和
for (int i = 1;i <= n;++ i)
for (int j = i;j <= n;j += i)
d[]j ++,s[j] += i;
欧拉筛法
void sieve(int n){
for (int i = 2;i <= n;i ++){
if (!vis[i])
prime[++ pn] = i;
for (int j = 1;j <= pn&& i * prime[j] <= n;j ++){
vis[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
欧拉筛法求约数及其和
不经常用,略...
update7/26:考试居然考了(虽然数据水,没用过了),我很震惊....所以我还是写吧。
/*约数个数*/
for (int i = 2;i <= b;i ++){
if (!vis[i]){
pri[++ cnt] = i;
num[i] = 1;
d[i] = 2;
}
for (int j = 1;j <= cnt && 1ll * i * pri[j] <= b;j ++){
vis[pri[j] * i] = 1;
if (i % pri[j] == 0){
num[pri[j] * i] = num[i] + 1;
d[pri[j] * i] = d[i] / (num[i] + 1) * (num[i] + 2);
break;
}
d[pri[j] * i] = d[i] * 2;
num[i] = 1;
}
}
/*约数和*/
s[1] = 1;
for(int i = 2;i <= n;i ++){
if (!vis[i]){
pri[++ cnt] = i;
s[i] = i + 1;
psum[i] = i + 1;
}
for (int j = 1;j <= cnt && 1ll * i * pri[j] <= n;j ++){
vis[pri[j] * i] = 1;
if (i % pri[j] == 0){
psum[pri[j] * i] = psum[i] * pri[j] + 1;
s[pri[j] * i] = s[i] / psum[i] * psum[pri[j] * i];
break;
}
s[pri[j] * i] = s[i] * (pri[j] + 1);
psum[pri[j] * i] = pri[j] + 1;
}
}
辗转相除法
int gcd(int a,int b){
if (b == 0)
return a;
return gcd(b,a % b);
}
int lcm(int a,int b){
return a / gcd(a,b) * b;
}
欧拉函数
求1到n中与n互质的数
int phi(int n){
int res = n;
for (int i = 2;i * i <= n;i ++){
if (n % i == 0){
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1)
res = res / n * (n - 1);
return res;
}
void sieve(int n){
phi[1] = 1;
for (int i = 2;i <= n;i ++){
if (!vis[i]){
pri[++ pn] = i;
phi[i] = i - 1;
}
for (int j = 1;j <= pn&& i * pri[j] <= n;j ++){
vis[i * pri[j]] = 1;
if (i % pri[j] == 0){
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
else
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
Miller_Rabin
判断素数
long long qkpow(long long x,long long y,long long mod){
long long ans = 1;
while (y){
if (y % 2 == 1)
ans = ans * x % mod;
x = x * x % mod;
y /=2;
}
return ans;
}
bool Miller_Rabin(int x){
if (x == 2 || x == 3 || x == 5 || x == 7)
return 1;
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0)
return 0;
long long m = x - 1,k = 0;
while (m % 2 == 0){
k ++;
m /= 2;
}
for (int i = 1;i <= 10;i ++){
long long a = rand() % (n - 1) + 1;
long long xx = qkpow(a,m,x);
long long y;
for (int j = 1;j <= k ;j ++){
y = xx * xx % x;
if (y == 1 && xx != 1 && xx != x - 1)
return 0;
xx = y;
}
if (y != 1)
return 0;
}
return 1;
}
拓展欧几里得
求解二元一次不定方程一组特解
int exgcd(int a,int b,int &x,int &y){
if (!b){
x = 1,y = 0;
return a;
}
else {
r = exgcd(b,a % b,y,x);
y -= x * (a - b);
return r;
}
}
逆元
ab %p == 1,称a,b在模p意义下互为逆元。
高斯消元
解方程模板
异或线性基
不会...没打过...略...
杨辉三角
组合数,计算系数
void initial (){
int i,j;
fr (int i = 0;i <= maxn;++ i)
c[i][0] = 1;
for (int i = 1;i <= maxn;++ i)
for (int j = 1;j <= maxn;++ j)
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
预处理阶乘
阶乘及其逆元。模P意义下
void prepare(){
fac[0] = rfac[0] = fac[1] = rfac[1] = 1;
for (int i = 2;i <= n;i ++){
fac[i] = 1ll * i * fac[i - 1] % p;
rfac[i] = 1ll * rfac[p % i] * (p - p / i) % p;
}
for (int i = 2;i <= n;i ++)
rfac[i] = 1ll * rfac[i] * rfac[i - 1] % p;
}
int c(int n,int m){
return 1ll * fac[n] * rfac[n - m] % p * rfac[m] % p;
}
Lucas
组合数C(n,m)%p,适用于n,m很大,p在10w左右
int Lucas(int n,int m){
if (m == 0 || n == m)
return 1;
else
return 1ll * C(n % p,m % p) * Lucas(n / p,m / p) % p;
}
Legendre
这不是超神(legendary)定理
求阶乘的质因数分解
for (int i = 1;i <= cnt;i ++)
for (long long j = pri[i];j <= n;j *= pri[i])
s[i] += n / j;