古代猪文

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2077 字
给定N,G，求G^)对999911659取模
一本通
例
正文

/*
原题：T1651「一本通 6.6 例 4」古代猪文
题意：给定 N,G，求 G^(Σ_{d|N} C(N,d)) 对 999911659 取模的结果。
思路：模数 P=999911659 是素数，由费马小定理只需知道指数对 P-1 取模的值。
P-1=999911658=2×3×4679×35617，把四个素因子分别作为模数用 Lucas 求出
Σ_{d|N} C(N,d)，再用 CRT 合并回对 P-1 取模的指数，最后快速幂求答案。
复杂度：时间 O(√N·log N + maxPrime)，空间 O(maxPrime)
易错点：1) 指数要模 P-1 而不是模 P，这是费马小定理的要求；
2) CRT 合并时 inv(M/p_i) 要在模 p_i 下求，不能全用一个模；
3) 枚举约数到 √N 即可，注意 i 与 N/i 相同的情况只计一次。
*/
#include <bits/stdc++.h>
using namespace std;
const long long P=999911659;
const long long PM=P-1;
const int PR[4]={2,3,4679,35617};
long long qpow(long long a,long long n,long long mod){
    long long r=1%mod;
    a%=mod;
    while(n>0){
        if(n&1){
            r=r*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return r;
}
vector<long long> fact,ifact;
long long smallC(long long n,long long m,long long p){
    if(m>n){
        return 0;
    }
    return fact[n]*ifact[m]%p*ifact[n-m]%p;
}
long long lucas(long long n,long long m,long long p){
    if(m<0 || m>n){
        return 0;
    }
    long long res=1;
    while(n>0 || m>0){
        res=res*smallC(n%p,m%p,p)%p;
        n/=p;
        m/=p;
    }
    return res;
}
long long calcSum(long long N,long long p){
    fact.assign(p,1);
    for(long long i=1;i<p;i++){
        fact[i]=fact[i-1]*i%p;
    }
    ifact.assign(p,1);
    ifact[p-1]=qpow(fact[p-1],p-2,p);
    for(long long i=p-2;i>=0;i--){
        ifact[i]=ifact[i+1]*(i+1)%p;
    }
    long long sum=0;
    for(long long i=1;i*i<=N;i++){
        if(N%i==0){
            sum=(sum+lucas(N,i,p))%p;
            long long j=N/i;
            if(j!=i){
                sum=(sum+lucas(N,j,p))%p;
            }
        }
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N,G;
    cin>>N>>G;
    long long exp=0;
    for(int i=0;i<4;i++){
        long long p=PR[i];
        long long ai=calcSum(N,p);
        long long mi=PM/p;
        // x = ai (mod p)，求 x 分量在 mod PM 下的贡献
        long long inv=mi%p==0?0:qpow(mi%p,p-2,p);
        exp=(exp+ai*mi%PM*inv%PM)%PM;
    }
    cout<<qpow(G,exp,P)<<"\n";
    return 0;
}
古代猪文

正文

一本通·提高篇的其它内容
