SDOI2010 古代猪文

答案为 $G^{\sum\limits_{d|n} \binom{n}{d} } \bmod 999911659$。根据欧拉定理得 $G^{\sum\limits_{d|n} \binom{n}{d}} \equiv G^{\sum\limits_{d|n} \binom{n}{d} \bmod 999911658} \pmod{999911659}$ 将 $999911658$ 质因数分解为 $2*3*4679*35617$,用 Lucas 定理计算出 $\binom{n}{d}$ 在分别模这四个质数意义下的值,使用 CRT 合并答案,最后快速幂即可。

#include <iostream>
#include <cstdio>
#include <cmath>

typedef long long LL;
#define int LL

const int MOD = 999911659;

int G, N;
int mod_num[6] = {0, 2, 3, 4679, 35617, MOD}, fact[5][36000];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

int fast_pow(int a, int b, int mod) {
  mod = mod_num[mod];
  int res = 1, base = a % mod;
  while (b > 0) {
    if (b & 1) res = 1LL * res * base % mod;
    base = 1LL * base * base % mod;
    b >>= 1;
  }
  return res;
}

int C(int a, int b, int mod) {
  if (a < b) return 0;
  return 1LL * fact[mod][a] * fast_pow(fact[mod][a - b], mod_num[mod] - 2, mod) % mod_num[mod] * fast_pow(fact[mod][b], mod_num[mod] - 2, mod) % mod_num[mod];
}

int Lucas(int a, int b, int mod) {
  if (!b) return 1;
  return 1LL * Lucas(a / mod_num[mod], b / mod_num[mod], mod) * C(a % mod_num[mod], b % mod_num[mod], mod) % mod_num[mod];
}

int CRT(int x, int y) {
  int a[5];
  for (int i = 1; i <= 4; ++i) a[i] = Lucas(x, y, i);
  int LCM = mod_num[5] - 1;
  int res = 0;
  for (int i = 1; i <= 4; ++i) {
    res = (res + 1LL * (LCM / mod_num[i]) * fast_pow(LCM / mod_num[i], mod_num[i] - 2, i) * a[i]) % LCM;
  }
  return res;
}

int calc(int x) {
  int sqr = sqrt(x);
  int res = 0;
  for (int i = 1; i <= sqr; ++i) {
    if (x % i == 0) {
      // printf("i=%d j=%d\n", i, x / i);
      res = (res + CRT(x, i)) % (mod_num[5] - 1);
      if (x / i != i) res = (res + CRT(x, x / i)) % (mod_num[5] - 1);
    }
  }
  return res;
}

signed main() {
  N = read();
  G = read();
  if (G % 999911659 == 0) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= 4; ++i) {
    fact[i][0] = 1;
    for (int j = 1; j <= mod_num[4]; ++j) {
      fact[i][j] = 1LL * fact[i][j - 1] * j % mod_num[i];
    }
  }
  printf("%lld", fast_pow(G, calc(N), 5));
  return 0;
}
最后修改:2019 年 09 月 21 日 10 : 23 AM

发表评论