一些数学 | Sprooc

快速幂

int pow(int a, int b, int m) {
  int ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) ans = (LL)ans * a % m;
    a = (LL)a * a % m;
  }
  return ans;
}

龟速乘

LL mul(LL a, LL b, LL p) {
  a %= p;
  b %= p;
  LL c = (double)a * b / p;
  LL x = a * b;
  LL y = c * p;
  LL ans = (LL)(x % p) - (LL)(y % p);
  if (ans < 0) ans += p;
  return ans;
}

等比数列（公比为p，项数为e，以1为首项）

int sum(int p, int e, int m) {
  if (e == 1) return 1;
  if (e % 2 == 0) {
    return (LL)(1 + pow(p, e / 2, m)) * sum(p, e / 2, m) % m;
  } else {
    return ((LL)(1 + pow(p, e / 2, m)) * sum(p, e / 2, m) % m +
            pow(p, e - 1, m)) % m;
  }
}

分解质因数

int s = 0;
for (int i = 2; i <= a / i; i++) {
  if (a % i != 0) continue;
  p[s] = i; c[s] = 0;
  while (a % i == 0) {
    a /= i; c[s]++;
  }
  s++;
}
if (a > 1) {
  p[s] = a; c[s++]++;
}