数学
CCDV2
7月 25, 2018
素数筛 + 质因数分解
由此可以引出来的知识点唯一分解定理 – 约数个数
typedef long long LL; const int MAXN = 1e5 + 100; const int MAXBOUND = 1e5 + 50; int prime[MAXN], total; bool check[MAXN]; void getPrime()//1 ~ total { memset(check, 1, sizeof(check)); for(LL i = 2; i <= MAXBOUND; ++i) { if(check[i]) { ++total; prime[total] = i; } for(LL j = 1; j <= total && i * prime[j] <= MAXBOUND; ++j) { check[i * prime[j]] = false; if(i % prime[j] == 0) break; } } } int a[MAXN], b[MAXN], tot; void getFactor(LL t)// 0 ~ tot-1 { int i = 1; LL cnt = 0; while(prime[i] < t && i <= total) { if(t % prime[i] == 0) { cnt = 0; a[tot] = prime[i]; while(t % prime[i] == 0) { ++cnt; t /= prime[i]; } b[tot] = cnt; ++tot; } ++i; } if(t != 1) { a[tot] = t; b[tot] = 1; ++tot; } }相关例题
TODO
欧拉函数
const int MAXN = 1e6 + 10; const int MAXBOUND = 1e6 + 1; int phi[MAXN], minDiv[MAXN]; void getPhi() { for(int i = 1; i <= MAXBOUND; ++i) { minDiv[i] = i; } for(int i = 2; i * i < MAXBOUND; ++i) { if(minDiv[i] == i) { for(int j = i * i; j < MAXBOUND; j += i) { minDiv[j] = i; } } } phi[1] = 1; for(int i = 2; i < MAXBOUND; ++i) { phi[i] = phi[i / minDiv[i]]; if((i / minDiv[i]) % minDiv[i] == 0) { phi[i] *= minDiv[i]; } else { phi[i] *= minDiv[i] - 1; } } }最大公约数、最小公倍数相关
快速幂
LL quickPow(LL a, LL i) { LL ret = 1; while(i) { if(i & 1) { ret = ret * a % mod; } a = a * a % mod; i /= 2; } return ret; }逆元
对于p是质数（一般mod都是质数）LL getInverse(LL t) { return quickPow(t, mod - 2); }对于a n互质
LL extendGcd(LL a, LL b, LL x, LL y) { if(b == 0) { x = 1; y = 0; return a; } else { LL r = extendGcd(b, a % b, y, x); y -= x * (a / b); return r; } } LL getInverse(LL a, LL n) { LL x, y; extendGcd(a, n, x, y); x = (x % n + n) % n; return x; }有一个东西叫逆元线性筛
阶乘的逆元线性筛：LL fac[MAXN], invf[MAXN]; void getFactorial() { fac[0] = 1; for(LL i = 1; i < MAXN; ++i) { fac[i] = fac[i - 1] * i; fac[i] %= mod; } invf[MAXN - 1] = getInverse(fac[MAXN - 1]); for(LL i = MAXN - 2; i >= 0; --i) { invf[i] = invf[i + 1] * (i + 1) % mod; } }1 ~ n 的逆元线性筛(模p意义下)
LL inv[MAXN]; void getInverseN(int n, LL p) { inv[1] = 1; for(int i = 2; i <= n; ++i) { inv[i] = (p - p / i) * inv[p % i] % p; } }排列组合
LL getC(int n, int r) { if(r < 0 || r > n) return 0; LL ret = fac[n] * invf[r] % mod; ret = ret * invf[n - r] % mod; return ret; } LL getInverseC(int n, int r) { LL ret = fac[r] * fac[n - r] % mod; ret = ret * invf[n] % mod; return ret; } LL getP(int n, int r) { LL ret = fac[n] * invf[r] % mod; return ret; }容斥原理
莫比乌斯反演
typedef long long LL; const int MAXN = 1e5 + 100; const int MAXBOUND = 1e5 + 50; int prime[MAXN], total, mu[MAXN]; bool check[MAXN]; void getMobius() { mu[1] = 1; memset(check, 1, sizeof(check)); for(LL i = 2; i <= MAXBOUND; ++i) { if(check[i]) { ++total; prime[total] = i; mu[i] = -1; } for(LL j = 1; j <= total && i * prime[j] <= MAXBOUND; ++j) { check[i * prime[j]] = false; if(i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } } }矩阵类
//0 ~ n - 1 //必要时在运算符内加取模操作 struct Matrix { const static int MAXN = 40; ULL a[MAXN][MAXN];//注意类型 int n; void init(int _n) { n = _n; memset(a, 0, sizeof(a)); for(int i = 0; i < n; ++i) a[i][i] = 1; } void clear(int _n = 0) { n = _n; memset(a, 0, sizeof(a)); } Matrix operator +(const Matrix &rhs) const { Matrix temp; temp.n = n; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) temp.a[i][j] = a[i][j] + rhs.a[i][j]; return temp; } Matrix operator -(const Matrix &rhs) const { Matrix temp; temp.n = n; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) temp.a[i][j] = a[i][j] - rhs.a[i][j]; return temp; } Matrix operator *(const Matrix &rhs) const { Matrix temp; temp.clear(); temp.n = n; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) for(int k = 0; k < n; ++k) temp.a[i][j] += a[i][k] * rhs.a[k][j]; return temp; } }; Matrix quickPow(Matrix a, int i) { Matrix temp; temp.init(a.n); while(i) { if(i & 1) { temp = temp * a; } a = a * a; i /= 2; } return temp; }高精度非负整数
const int ten[4] = {1, 10, 100, 1000}; struct BigNumber { const static int MAXL = 1e3; int d[MAXL]; BigNumber(string s) { int len = s.size(); d[0] = (len - 1) / 4 + 1; for(int i = 1; i < MAXL; ++i) d[i] = 0; for(int i = len - 1, j, k; i >= 0; --i) { j = (len - i - 1) / 4 + 1; k = (len - i - 1) % 4; d[j] += ten[k] * (s[i] - '0'); } while(d[0] > 1 && d[d[0]] == 0) --d[0]; } BigNumber() { *this = BigNumber(string("0")); } string toString() { string s(""); int i, j, temp; for(i = 3; i >= 1; --i) if(d[d[0]] >= ten[i]) break; temp = d[d[0]]; for(j = i; j >= 0; --j) { s = s + (char)(temp / ten[j] + '0'); temp %= ten[j]; } for(i = d[0] - 1; i > 0; --i) { temp = d[i]; for(j = 3; j >= 0; --j) { s = s + char(temp / ten[j] + '0'); temp %= ten[j]; } } return s; } BigNumber operator *(int k); } zero("0"); bool operator <(const BigNumber &lhs, const BigNumber &rhs) { if(lhs.d[0] != rhs.d[0]) return lhs.d[0] < rhs.d[0]; for(int i = lhs.d[0]; i > 0; --i) { if(lhs.d[i] != rhs.d[i]) return lhs.d[i] < rhs.d[i]; } return false; } BigNumber operator +(const BigNumber &lhs, const BigNumber &rhs) { BigNumber ret; ret.d[0] = max(lhs.d[0], rhs.d[0]); int x = 0; for(int i = 1; i <= ret.d[0]; ++i) { x = lhs.d[i] + rhs.d[i] + x; ret.d[i] = x % 10000; x /= 10000; } while(x != 0) { ret.d[++ret.d[0]] = x % 10000; x /= 10000; } return ret; } BigNumber operator -(const BigNumber &lhs, const BigNumber &rhs) { BigNumber ret; ret.d[0] = lhs.d[0]; int x = 0; for(int i = 1; i <= ret.d[0]; ++i) { x = 10000 + lhs.d[i] - rhs.d[i] + x; ret.d[i] = x % 10000; x = x / 10000 - 1; } while((ret.d[0] > 1) && (ret.d[ret.d[0]] == 0)) --ret.d[0]; return ret; } BigNumber operator *(const BigNumber &lhs, const BigNumber &rhs) { BigNumber ret; ret.d[0] = lhs.d[0] + rhs.d[0]; for(int i = 1; i <= lhs.d[0]; ++i) { int x = 0; for(int j = 1; j <= rhs.d[0]; ++j) { x = lhs.d[i] * rhs.d[j] + x + ret.d[i + j - 1]; ret.d[i + j - 1] = x % 10000; x /= 10000; } ret.d[i + rhs.d[0]] = x; } while((ret.d[0] > 1) && (ret.d[ret.d[0]] == 0)) --ret.d[0]; return ret; } bool smaller(const BigNumber &lhs, const BigNumber &rhs, int delta) { if(lhs.d[0] + delta != rhs.d[0]) return lhs.d[0] + delta < rhs.d[0]; for(int i = lhs.d[0]; i > 0; --i) { if(lhs.d[i] != rhs.d[i + delta]) return lhs.d[i] < rhs.d[i + delta]; } return true; } void _minus(BigNumber &lhs, BigNumber &rhs, int delta) { int x = 0; for(int i = 1; i <= lhs.d[0] - delta; ++i) { x = 10000 + lhs.d[i + delta] - rhs.d[i] + x; lhs.d[i + delta] = x % 10000; x = x / 10000 - 1; } while(lhs.d[0] > 1 && lhs.d[lhs.d[0]] == 0) --lhs.d[0]; } BigNumber BigNumber::operator *(int k) { BigNumber ret; ret.d[0] = d[0]; int x = 0; for(int i = 1; i <= d[0]; ++i) { x = d[i] * k + x; ret.d[i] = x % 10000; x /= 10000; } while(x > 0) { ret.d[++ret.d[0]] = x % 10000; x /= 10000; } while(ret.d[0] > 1 && ret.d[ret.d[0]] == 0) --ret.d[0]; return ret; } //除法运算 余数在residue中 BigNumber residue, mid1[15]; BigNumber operator /(const BigNumber &lhs, const BigNumber &rhs) { BigNumber ret; residue = lhs; mid1[0] = rhs; for(int i = 1; i <= 13; ++i) { mid1[i] = mid1[i - 1] * 2; } for(int i = lhs.d[0] - rhs.d[0]; i >= 0; --i) { int temp = 8192; for(int j = 13; j >= 0; --j) { if(smaller(mid1[j], residue, i)) { _minus(residue, mid1[j], i); ret.d[i + 1] += temp; } temp /= 2; } } ret.d[0] = max(1, lhs.d[0] - rhs.d[0] + 1); while(ret.d[0] > 1 && ret.d[ret.d[0]] == 0) --ret.d[0]; return ret; } bool operator ==(const BigNumber &lhs, const BigNumber &rhs) { if(lhs.d[0] != rhs.d[0]) return false; for(int i = 1; i <= lhs.d[0]; ++i) { if(lhs.d[i] != rhs.d[i]) return false; } return true; }