代码模板
数论
快速幂
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
线性筛法(素数+欧拉函数)
int st[N1], pri[N1], cnt, phi[N1];
int getp(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i ++ ) {
if (!st[i]) pri[ ++ cnt] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt && pri[j] <= n / i; j ++ ) {
st[pri[j] * i] = true;
if (i % pri[j] == 0) {
phi[pri[j] * i] = phi[i] * pri[j];
break;
}
phi[pri[j] * i] = phi[i] * (pri[j] - 1);
}
}
}
扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
/*
int d = exgcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
*/
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
欧拉函数(一个数)
int phi_(int x) {
int phi = x;
for (int i = 2; i <= x / i; i ++ ) {
if (x % i == 0) {
phi = phi * (i - 1) / i;
while (x % i == 0) x /= i;
}
}
if (x > 1) phi = phi * (x - 1) / x;
return phi;
}
递推求逆元
void getinv(int n, int p) {
inv[1] = 1;
for (int i = 2; i <= n; i ++ ) inv[i] = inv[p % i] * (p - p / i) % p;
}
标签:phi,return,int,res,代码,exgcd,N1,模板
From: https://www.cnblogs.com/MingruiYang/p/17986832