古代猪文 | Hexo

归档于 2019-07-23 17:38

题意：

给定q ，n 求$q^{\sum\limits {d|n} C_{n}^{d} }mod 999911659$

题解：

首先如果你直接算次方上的数的话会炸掉，因为欧拉定理我们可以得到

$q^{\sum\limits {d|n} C_{n}^{d} mod999911658}mod 999911659$

因为mod的数是个合数

我们尝试分解质因数 $999911658=2\times 3\times 4679\times 35617$

遇到这种式子不要急着$ex_lucas$，观察性质，$999911658 $中分解的数都为$1$次

所以我们可以直接用$lucas$求出来$mod$ $2$，$3$，$4679$，$35617$下各自的值，最后中国剩余定理合并即可

具体实现看代码

代码：

#include<bits/stdc++.h>
#define ll long long
#define A 40000
ll a[A],b[A],k,p,n;
ll w[6]={0,2,3,4679,35617,999911659};
ll jie[5][A],ni[5][A];
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-a/b*y;
    return gcd;
}
ll meng(ll x,ll k,ll cix){
    ll ans=1;
    for(;k;k>>=1,x=x*x%w[cix])
        if(k&1)
            ans=ans*x%w[cix];
    return ans;
}
ll china(){
    ll x,y,a=0,m,n=1;
    for(ll i=1;i<=4;i++)
        n*=w[i];
    for(ll i=1;i<=4;i++){
        m=n/w[i];
        exgcd(w[i],m,x,y);
        a=(a+y*m*b[i])%n;
    }
    if(a>0) return a;
    return a+n;
}
ll jic(ll n,ll m,ll cix){
    if(m>n) return 0;
    if(m==0) return 1;
//    printf("jie=%lld ni=%lld ni2=%lld n=%lld m=%lld\n",jie[cix][n],ni[cix][n-m],ni[cix][m],n,m);
    return jie[cix][n]%w[cix]*ni[cix][n-m]%w[cix]*ni[cix][m]%w[cix];
}
ll lucas(ll n,ll m,ll cix){
    if(n==0)return 1;
//    printf("jic=%lld n=%lld m=%lld cix=%lld n=%lld m=%lld\n",jic(n%w[cix],m%w[cix],cix),n%w[cix],m%w[cix],cix,n,m);
    return jic(n%w[cix],m%w[cix],cix)*lucas(n/w[cix],m/w[cix],cix)%w[cix];
}
using namespace std;
int main()
{
    scanf("%lld%lld",&n,&p);
    if(n==999911659){
        cout<<0<<endl;
        return 0;
    }
    for(ll i=1;i<=4;i++){
        jie[i][0]=1;
        ni[i][0]=1;
        for(ll j=1;j<w[i];j++)
            jie[i][j]=jie[i][j-1]*j%w[i];
        ni[i][w[i]-1]=meng(jie[i][w[i]-1],w[i]-2,i);
//        printf("jie=%lld ni=%lld\n",jie[i][w[i]-1],ni[i][w[i]-1]);
        for(ll j=w[i]-2;j>=1;j--){
            ni[i][j]=ni[i][j+1]*(j+1)%w[i];
//if(j>=35600)            printf("ni[%lld][%lld]=%lld\n",i,j,ni[i][j]);
        }
        for(ll j=1;j*j<=n;j++){
            if((n%j)==0){
//                printf("luc=%lld i=%lld j=%lld\n",lucas(n,j,i),i,j);
                (b[i]+=lucas(n,j,i))%=w[i];            
                if(j*j!=n){
                    (b[i]+=lucas(n,n/j,i))%=w[i];
                }
            }
//            printf("b[%lld]=%lld j=%lld\n",i,b[i],j);

//            printf("b[%lld]=%lld j=%lld\n",i,b[i],j);
        }
    }
//    for(ll i=1;i<=4;i++)
//        printf("%lld\n",b[i]);
    ll j=china();
//    cout<<j<<endl;
    ll k=meng(p,china(),5);
    cout<<k<<endl;
    //模w「i」 剩余b「i」    
}