[BZOJ 1951][Sdoi2010]古代猪文 混合数论

传送门·Teleport!

题目描述

给出N,G,求:
$$ G^{\sum_{d|N}C(N,\frac{N}{d})}\mod 999911659 $$

解题报告

老样子，附赠样例！

Input:
71723 1931
Output:
948504873

混合数论题
首先发现模数是个大质数，必然和G互质，可以用欧拉定理降幂
降幂之后难点是求指数，指数现在是
$$\sum_{d|N}C(N,\frac{N}{d}) \mod 999911658$$
然后发现模数不是质数了，什么都不好搞了
卡了一会。。观察999911658这个数，发现此数可以分解成四个互不相同的质因数并且每个数都小于40000
JeremyGuo突然激动：这不是中国剩余定理么！
插入中国剩余定理(以下内容来自 ACDreamer )：
设正整数m1,m2,..mn两两互质,方程组 有唯一解，那么唯一解可以表示为
其中 ,Mi^-1是在模mi意义下的逆元。
那么对于这道题，分别求出指数模四个质数下的解，就可以分别使用Lucas定理进行计算，然后手算逆元进行合并了。

最后吐槽一下: 0.0必须特判G%999911659==0的情况，不然会无限wa！别问我为什么我也不知道%>_<%
接下来贴代码！

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

typedef long long LL;
const LL PRIME[4] = {2,3,4679,35617};
const LL INV[4] = {1, 1, 1353, 31254};
const LL ENTRYP = 999911658;
LL N, G;

LL advPow (LL a, int b, LL c) {
    a %= c;
    LL ret = 1;
    while(b) {
        if(b & 1) ret *= a, ret %= c;
        a *= a;
        a %= c;
        b >>= 1;
    }
    return ret%c;
}
LL fac_stor[4][40000], inv_stor[4][40000];
LL calC(int n, int m, int P, LL * fac, LL * inv) {
    if(m > n) return 0;
    if(n == m || m == 0) return 1;
    return fac[n]*advPow(fac[m]*fac[n-m]%P, P-2, P)%P;
}
LL lucas (int n, int m, int P, LL * fac, LL * inv) {
    if(m == 0) return 1;
    return lucas(n/P, m/P, P, fac, inv)*calC(n%P, m%P, P, fac, inv)%P;
}

#include <iostream>

LL sum = 0;LL ans[4];
void attachToAns (int fact) {
    //printf("fact: %d\n", fact);
    for(int pi = 0; pi<4; pi++) {
        LL P = PRIME[pi];
        ans[pi] += lucas(N, N/fact, P, fac_stor[pi], inv_stor[pi]);
        ans[pi] %= PRIME[pi];
    }
}

int main () {

    std :: cin >> N >> G;
    const LL PMOD = PRIME[0]*PRIME[1]*PRIME[2]*PRIME[3]+1;
    if(G == PMOD) {puts("0"); return 0;}
    for(int pi = 0; pi<4; pi++) {
        fac_stor[pi][0] = 1;
        for(int i = 1; i<PRIME[pi]; i++)
            fac_stor[pi][i] = fac_stor[pi][i-1]*(LL)i%PRIME[pi];
    }
    for(int i = 1; i*i<=N; i++)
        if(N % i == 0) {
            attachToAns(i);
            if(N/i != i) attachToAns(N/i);
        }
    sum = ans[0]*(ENTRYP/PRIME[0])%ENTRYP*INV[0]
        + ans[1]*(ENTRYP/PRIME[1])%ENTRYP*INV[1]
        + ans[2]*(ENTRYP/PRIME[2])%ENTRYP*INV[2]
        + ans[3]*(ENTRYP/PRIME[3])%ENTRYP*INV[3];
    sum %= ENTRYP;
    std :: cout << advPow(G, sum, PMOD) << '\n';
}