数学
快速幂
/** 快速幂 - 普通版* 2023-10-09: https://atcoder.jp/contests/tenka1-2017/submissions/46411797
**/
int power(int a, i64 b, int p) {int res = 1;for (; b; b /= 2, a = 1LL * a * a % p) {if (b % 2) {res = 1LL * res * a % p;}}return res;
}/** 快速幂 - 手写乘法* 2023-09-27: https://qoj.ac/submission/189343
**/
using i64 = long long;i64 mul(i64 a, i64 b, i64 p) {i64 c = a * b - i64(1.0L * a * b / p) * p;c %= p;if (c < 0) {c += p;}return c;
}i64 power(i64 a, i64 b, i64 p) {i64 res = 1;for (; b; b /= 2, a = mul(a, a, p)) {if (b % 2) {res = mul(res, a, p);}}return res;
}
基姆拉尔森公式
/** 基姆拉尔森公式* 2023-09-05: https://qoj.ac/submission/164735
**/
const int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool isLeap(int y) {return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}int daysInMonth(int y, int m) {return d[m - 1] + (isLeap(y) && m == 2);
}int getDay(int y, int m, int d) {int ans = 0;for (int i = 1970; i < y; i++) {ans += 365 + isLeap(i);}for (int i = 1; i < m; i++) {ans += daysInMonth(y, i);}ans += d;return (ans + 2) % 7 + 1;
}
欧拉筛
/** 欧拉筛* 2023-11-14: https://qoj.ac/submission/251234
**/
std::vector<int> minp, primes;void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}bool isprime(int n) {return minp[n] == n;
}/** 欧拉筛* 2023-03-22: https://yukicoder.me/submissions/851524
**/
void sieve(int n) {minp.assign(n + 1, 0);phi.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;phi[i] = i - 1;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {phi[i * p] = phi[i] * p;break;}phi[i * p] = phi[i] * (p - 1);}}for (int i = 2; i <= n; i++) {phi[i] += phi[i - 1];}
}
莫比乌斯函数筛（莫比乌斯反演）
/** 莫比乌斯函数筛（莫比乌斯反演）* 2023-03-04: https://atcoder.jp/contests/tupc2022/submissions/39391116* 2023-04-07: https://yukicoder.me/submissions/857472
**/
std::unordered_map<int, Z> fMu;std::vector<int> minp, primes, phi, mu;
std::vector<i64> sphi;void sieve(int n) {minp.assign(n + 1, 0);phi.assign(n + 1, 0);sphi.assign(n + 1, 0);mu.assign(n + 1, 0);primes.clear();phi[1] = 1;mu[1] = 1;for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;phi[i] = i - 1;mu[i] = -1;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {phi[i * p] = phi[i] * p;break;}phi[i * p] = phi[i] * (p - 1);mu[i * p] = -mu[i];}}for (int i = 1; i <= n; i++) {sphi[i] = sphi[i - 1] + phi[i];mu[i] += mu[i - 1];}
}Z sumMu(int n) {if (n <= N) {return mu[n];}if (fMu.count(n)) {return fMu[n];}if (n == 0) {return 0;}Z ans = 1;for (int l = 2, r; l <= n; l = r + 1) {r = n / (n / l);ans -= (r - l + 1) * sumMu(n / l);}return ans;
}
扩展欧几里得（exgcd）
/** 扩展欧几里得（exgcd）* 2024-08-07: https://codeforces.com/contest/1993/submission/275110715
**/
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {if (b == 0) {x = 1;y = 0;return a;}i64 g = exgcd(b, a % b, y, x);y -= a / b * x;return g;
}// ax + b = 0 (mod m)
std::pair<i64, i64> sol(i64 a, i64 b, i64 m) {assert(m > 0);b *= -1;i64 x, y;i64 g = exgcd(a, m, x, y);if (g < 0) {g *= -1;x *= -1;y *= -1;}if (b % g != 0) {return {-1, -1};}x = x * (b / g) % (m / g);if (x < 0) {x += m / g;}return {x, m / g};
}/** 扩展欧几里得（exgcd）* 2023-09-05: https://qoj.ac/submission/165983
**/
std::array<i64, 3> exgcd(i64 a, i64 b) {if (!b) {return {a, 1, 0};}auto [g, x, y] = exgcd(b, a % b);return {g, y, x - a / b * y};
}
