线性筛求素数

int prime[MAXN]; // 保存素数
bool is_not_prime[MAXN] = {1, 1}; // 0和1都不是素数

// 筛选 n 以内的所有素数
void xxs(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!is_not_prime[i]) { // 如果i是素数
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= n; ++j) {
            is_not_prime[i*prime[j]] = 1;
            // 如果i中包含了该质因子，则停止
            if (i % prime[j] == 0) break;
        }
    }
}

欧拉函数

求单个

int euler_phi(int n) {
  // 如果存在大于根号n的质因子，至多有一个
  int m = int(sqrt(n + 0.5));
  int ans = n;
  // 跟判定素数很像
  for (int i = 2; i <= m; i++) {
    // 如果i能整除n，则i是n的因子，也会质因子（看下面的while）
    if (n % i == 0) {
      ans = ans / i * (i - 1); // 根据定义计算
      // 根据唯一分解定理，去掉i的幂
      while (n % i == 0) n /= i;
    }
  }
  // 如果最后n>1，则为一个大于根号n的一个质因子
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

求多个

// 整体框架为线性筛素数的代码，中间根据欧拉函数的性质加了几条语句而已
int n, phi[N], prime[N], tot;
bool not_prime[N]; // true表示不是素数，false表示是素数
void getPhi() {
    int i, j, k;
    phi[1] = 1;
    for (i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            prime[++tot] = i;
            phi[i] = i-1; // 根据性质2
        }
        for (j = 1; j <= tot; ++j) {
            k = i * prime[j];
            if (k > n) break;
            not_prime[k] = true;
            if (i % prime[j] == 0) { // 变形1
                phi[k] = prime[j] * phi[i];
                break;
            } else { // 变形2
                phi[k] = (prime[j]-1) * phi[i];
            }
        }
    }
}

gcd求最大公约数

// 递归形式
int gcd(int x, int y) {
    return (y == 0 ? x : gcd(y, x%y));
}

// 非递归形式
int gcd(int x, int y) {
    int r = x % y; // 取余数
    while (r) { // 余数不为0，交换变量，继续做除法
        x = y;
        y = r;
        r = x % y;
    }
    return y; // 余数为0时，除数为gcd
}

乘法逆元

费马小定理求逆元

typedef long long ll;
ll quickpow(ll a, ll n, ll p) { //快速幂求 a^n % p
    ll ans = 1;
    while(n) {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

ll niyuan(ll a, ll p) { //费马小定理求逆元 a^(p-2)%p
    return quickpow(a, p - 2, p);
}

线性求1-n逆元

// 因为 1<i<p，所以 p/i 一定小于 p
ny[1] = 1;
for (int i = 2; i < p; ++i) {
    ny[i] = (long long)(p - p / i) * ny[p % i] % p; // 注意最后的模 p 不要忘记
}

中国剩余定理

物不知数问题

LL CRT(int k, LL a[], LL r[]) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

卢卡斯定理

求大组合数取模

// 需要先预处理出fact[]，即阶乘
ll C(ll n, ll m, ll p) {
    return n < m ? 0 : fact[n] * inv(fact[m], p) % p * inv(fact[n - m], p) % p;
}

ll Lucas(ll n, ll m, ll p) {
  if (m == 0) return 1;
  return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

详解网址
数论基础