LL n, a, ans; LL gcd(LL a, LL b){ return b ? gcd(b, a % b) : a; } intmain(){ cin >> n; for (int i = 0; i < n; i ++ ){ cin >> a; if (a < 0) a = -a; ans = gcd(ans, a); } cout << ans << "\n"; return0; }
逆元
费马小定理解(借助快速幂)
若 为素数,,则 。
另一个形式:对于任意整数 ,有 。
单次计算的复杂度即为快速幂的复杂度 。限制: 必须是质数,且需要满足 与 互质。
1
LL inv(LL x){ returnmypow(x, mod - 2, mod);}
扩展欧几里得解
此方法的 没有限制,复杂度为 ,但是比快速幂法常数大一些。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
int x, y; intexgcd(int a, int b, int &x, int &y){ //扩展欧几里得算法 if (b == 0) { x = 1, y = 0; return a; //到达递归边界开始向上一层返回 } int r = exgcd(b, a % b, x, y); int temp = y; //把x y变成上一层的 y = x - (a / b) * y; x = temp; return r; //得到a b的最大公因数 } LL getInv(int a, int mod){ //求a在mod下的逆元,不存在逆元返回-1 LL x, y, d = exgcd(a, mod, x, y); return d == 1 ? (x % mod + mod) % mod : -1; }
离线求解:线性递推解
以 的复杂度完成 中全部逆元的计算。
1 2 3
inv[1] = 1; for (int i = 2; i <= n; i ++ ) inv[i] = (p - p / i) * inv[p % i] % p;
扩展欧几里得 exgcd
求解形如 的不定方程的任意一组解。
1 2 3 4 5 6 7 8 9
intexgcd(int a, int b, int &x, int &y){ if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; }
namespace BSGS { LL a, b, p; map<LL, LL> f; inline LL gcd(LL a, LL b){ return b > 0 ? gcd(b, a % b) : a; } inline LL ps(LL n, LL k, int p){ LL r = 1; for (; k; k >>= 1) { if (k & 1) r = r * n % p; n = n * n % p; } return r; } voidexgcd(LL a, LL b, LL &x, LL &y){ if (!b) x = 1, y = 0; } else { exgcd(b, a % b, x, y); LL t = x; x = y; y = t - a / b * y; } } LL inv(LL a, LL b){ LL x, y; exgcd(a, b, x, y); return (x % b + b) % b; } LL bsgs(LL a, LL b, LL p){ f.clear(); int m = ceil(sqrt(p)); b %= p; for (int i = 1; i <= m; i++) { b = b * a % p; f[b] = i; } LL tmp = ps(a, m, p); b = 1; for (int i = 1; i <= m; i++) { b = b * tmp % p; if (f.count(b) > 0) return (i * m - f[b] + p) % p; } return-1; } LL exbsgs(LL a, LL b, LL p){ if (b == 1 || p == 1) return0; LL g = gcd(a, p), k = 0, na = 1; while (g > 1) { if (b % g != 0) return-1; k++; b /= g; p /= g; na = na * (a / g) % p; if (na == b) return k; g = gcd(a, p); } LL f = bsgs(a, b * inv(na, p) % p, p); if (f == -1) return-1; return f + k; } } // namespace BSGS
usingnamespace BSGS;
intmain(){ IOS; cin >> p >> a >> b; a %= p, b %= p; LL ans = exbsgs(a, b, p); if (ans == -1) cout << "no solution\n"; else cout << ans << "\n"; return0; }
欧拉函数
直接求解单个数的欧拉函数
到 中与 互质数的个数称为欧拉函数,记作 。求解欧拉函数的过程即为分解质因数的过程,复杂度 。
1 2 3 4 5 6 7 8 9 10 11
intphi(int n){ //求解 phi(n) int ans = n; for(int i = 2; i <= n / i; i ++) { //注意,这里要写 n / i ,以防止 int 型溢出风险和 sqrt 超时风险 if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } } if(n > 1) ans = ans / n * (n - 1); //特判 n 为质数的情况 return ans; }
#include<bits/stdc++.h> usingnamespace std; bool large_enough = false; // 判断是否有b >= phi(m) inlineintread(int MOD = 1e9 + 7)// 快速读入稍加修改即可以边读入边取模,不取模时直接模一个大于数据范围的数 { int ans = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { ans = ans * 10 + c - '0'; if (ans >= MOD) { ans %= MOD; large_enough = true; } c = getchar(); } return ans; } intphi(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; } intqpow(int a, int n, int MOD)// 快速幂 { int ans = 1; while (n) { if (n & 1) ans = 1LL * ans * a % MOD; // 注意防止溢出 n >>= 1; a = 1LL * a * a % MOD; } return ans; } intmain() { int a = read(), m = read(), phiM = phi(m), b = read(phiM); cout << qpow(a, b + (large_enough ? phiM : 0), m); return0; }
voiddivide(int n){ for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n / i; ++ j) f[i * j].push_back(i); for (int i = 1; i <= n; ++ i) { for (auto it : f[i]) cout << it << " "; cout << endl; } } intmain(){ int x; cin >> x; divide(x); return0; }
试除法判是否是质数
标准解
。
1 2 3 4 5 6 7
boolis_prime(int n){ if (n < 2) returnfalse; for (int i = 2; i <= x / i; i++) { if (n % i == 0) returnfalse; } returntrue; }
常数优化法
常数优化,达到 。
1 2 3 4 5 6 7 8 9 10 11
boolis_prime(int n){ if (n < 2) returnfalse; if (n == 2 || n == 3) returntrue; if (n % 6 != 1 && n % 6 != 5) returnfalse; for (int i = 5, j = n / i; i <= j; i += 6) { if (n % i == 0 || n % (i + 2) == 0) { returnfalse; } } returntrue; }
int n; LL ai[maxn], bi[maxn]; inlineintmypow(int n, int k, int p){ int r = 1; for (; k; k >>= 1, n = n * n % p) if (k & 1) r = r * n % p; return r; } LL exgcd(LL a, LL b, LL &x, LL &y){ if (b == 0) { x = 1, y = 0; return a; } LL gcd = exgcd(b, a % b, x, y), tp = x; x = y, y = tp - a / b * y; return gcd; } LL excrt(){ LL x, y, k; LL M = bi[1], ans = ai[1]; for (int i = 2; i <= n; ++ i) { LL a = M, b = bi[i], c = (ai[i] - ans % b + b) % b; LL gcd = exgcd(a, b, x, y), bg = b / gcd; if (c % gcd != 0) return-1; x = mul(x, c / gcd, bg); ans += x * M; M *= bg; ans = (ans % M + M) % M; } return (ans % M + M) % M; } intmain(){ cin >> n; for (int i = 1; i <= n; ++ i) cin >> bi[i] >> ai[i]; cout << excrt() << endl; return0; }
求解连续按位异或
以 复杂度计算 。
1 2 3 4 5
unsignedxor_n(unsigned n){ unsigned t = n & 3; if (t & 1) return t / 2u ^ 1; return t / 2u ^ n; }
constint SIZE = 2; structMatrix { ll M[SIZE + 5][SIZE + 5]; voidclear(){ memset(M, 0, sizeof(M)); } voidreset(){ //初始化 clear(); for (int i = 1; i <= SIZE; ++i) M[i][i] = 1; } Matrix friendoperator*(const Matrix &A, const Matrix &B) { Matrix Ans; Ans.clear(); for (int i = 1; i <= SIZE; ++i) for (int j = 1; j <= SIZE; ++j) for (int k = 1; k <= SIZE; ++k) Ans.M[i][j] = (Ans.M[i][j] + A.M[i][k] * B.M[k][j]) % mod; return Ans; } Matrix friendoperator+(const Matrix &A, const Matrix &B) { Matrix Ans; Ans.clear(); for (int i = 1; i <= SIZE; ++i) for (int j = 1; j <= SIZE; ++j) Ans.M[i][j] = (A.M[i][j] + B.M[i][j]) % mod; return Ans; } };
inlineintmypow(LL n, LL k, int p = MOD){ LL r = 1; for (; k; k >>= 1, n = n * n % p) { if (k & 1) r = r * n % p; } return r; } bool ok = 1; Matrix getinv(Matrix a){ //矩阵求逆 int n = SIZE, m = SIZE * 2; for (int i = 1; i <= n; i++) a.M[i][i + n] = 1; for (int i = 1; i <= n; i++) { int pos = i; for (int j = i + 1; j <= n; j++) if (abs(a.M[j][i]) > abs(a.M[pos][i])) pos = j; if (i != pos) swap(a.M[i], a.M[pos]); if (!a.M[i][i]) { puts("No Solution"); ok = 0; } ll inv = q_pow(a.M[i][i], mod - 2); for (int j = 1; j <= n; j++) if (j != i) { ll mul = a.M[j][i] * inv % mod; for (int k = i; k <= m; k++) a.M[j][k] = ((a.M[j][k] - a.M[i][k] * mul) % mod + mod) % mod; } for (int j = 1; j <= m; j++) a.M[i][j] = a.M[i][j] * inv % mod; } Matrix res; res.clear(); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) res.M[i][j] = a.M[i][n + j]; return res; }
intmul(int a, int b, int m){ int r = a * b - m * (int)(1.L / m * a * b); return r - m * (r >= m) + m * (r < 0); } intmypow(int a, int b, int m){ int res = 1 % m; for (; b; b >>= 1, a = mul(a, a, m)) { if (b & 1) { res = mul(res, a, m); } } return res; }
int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23}; boolMR(int n){ if (n <= 1) return0; for (int p : B) { if (n == p) return1; if (n % p == 0) return0; } int m = (n - 1) >> __builtin_ctz(n - 1); for (int p : B) { int t = m, a = mypow(p, m, n); while (t != n - 1 && a != 1 && a != n - 1) { a = mul(a, a, n); t *= 2; } if (a != n - 1 && t % 2 == 0) return0; } return1; }
intPR(int n){ for (int p : B) { if (n % p == 0) return p; } auto f = [&](int x) -> int { x = mul(x, x, n) + 1; return x >= n ? x - n : x; }; int x = 0, y = 0, tot = 0, p = 1, q, g; for (int i = 0; (i & 255) || (g = gcd(p, n)) == 1; i++, x = f(x), y = f(f(y))) { if (x == y) { x = tot++; y = f(x); } q = mul(p, abs(x - y), n); if (q) p = q; } return g; } vector<int> fac(int n){ #define pb emplace_back if (n == 1) return {}; if (MR(n)) return {n}; int d = PR(n); auto v1 = fac(d), v2 = fac(n / d); auto i1 = v1.begin(), i2 = v2.begin(); vector<int> ans; while (i1 != v1.end() || i2 != v2.end()) { if (i1 == v1.end()) { ans.pb(*i2++); } elseif (i2 == v2.end()) { ans.pb(*i1++); } else { if (*i1 < *i2) { ans.pb(*i1++); } else { ans.pb(*i2++); } } } return ans; }