bzoj1951 题目描述：给定n和g，求\(g^{\sum_{i = 1}^n i|n C_{n}^{i}}\) mod 999911659
输入格式：一行两个数，分别表示n和g
输出格式：一行一个整数，表示答案mod 999911659后的结果
输入样例： 4 2
输出样例： 2048
解析：直接计算组合数肯定不行，那要怎么办呢？ 根据欧拉定理的推论可知，\(g^{\sum_{i = 1}^n i|n C_{n}^{i}}\) \(\equiv\) \(g^{\sum_{i = 1}^n i|n C_{n}^{i}mod 999911658}\) mod 999911659 而999911658 = 2 \(\times\) 3 \(\times\) 4679 \(\times\) 35617，这样就将模数缩小，可以直接用lucas定理进行计算 算出结果对4个模数的结果后，再用中国剩余定理将结果合并即可。
代码如下：
#include<cstdio> using namespace std; const int MOD = 999911659; const int b[] = {2, 3, 4679, 35617}; int g, n, fac[40005], ans, a[5]; int ksm(int x, int y, int p) { //快速幂 int res = 1, base = x; while (y) { if (y & 1) res = 1ll * res * base % p; base = 1ll * base * base % p; y >>= 1; } return res; } int C(int x, int y, int p) { //算组合数 if (y > x) return 0; int inv = 1ll * ksm(fac[y], p - 2, p) * ksm(fac[x - y], p - 2, p) % p; return 1ll * fac[x] * inv % p; } int lucas(int x, int y, int p) { //lucas定理 if (y > x) return 0; if (!x) return 1; return 1ll * lucas(x / p, y / p, p) * C(x % p, y % p, p) % p; } void crt(void) { //中国剩余定理 for (int i = 0; i < 4; ++ i) { ans += 1ll * a[i] * ((MOD - 1) / b[i]) % (MOD - 1) * ksm((MOD - 1) / b[i], b[i] - 2, b[i]) % (MOD - 1); ans %= MOD - 1; } } int main() { scanf("%d %d", &n, &g); fac[0] = 1; if (g % MOD == 0) return printf("0"),0; for (int j = 0; j < 4; ++ j) { //枚举4个模数计算答案 for (int i = 1; i <= b[j]; ++ i) fac[i] = 1ll * fac[i - 1] * i % b[j]; for (int i = 1; 1ll * i * i <= n; ++ i) { if (n % i) continue; a[j] = (a[j] + lucas(n, i, b[j])) % b[j]; if (n / i != i) a[j] = (a[j] + lucas(n, n / i, b[j])) % b[j]; } } crt(); printf("%d", ksm(g, ans, MOD)); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9933052.html
相关资源：JAVA上百实例源码以及开源项目