about 4 years ago

orzlyd神犇的题解
写啊写啊发现什么都不会了sigh
QAQ因为枚举因子的错误还挂了一发
中国剩余定理当sum%mod==0时返回mod还是返回0是一个需要注意的问题

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define Mod 999911659
#define LL long long 
using namespace std;
const int p[4]={2,3,4679,35617};
int s[4],n,g;
int jc[36000][4];
inline int mul(int x,int y,int mod)
{
    LL r=x*(LL)y%mod;
    return (int)r;
}
inline void exgcd(int a,int b,int &d,int &x,int &y)
{
    if (!b){d=a;x=1;y=0;}
    else{exgcd(b,a%b,d,y,x);y-=x*(a/b);} 
}
inline int inv(int x,int mod)
{
    int d,a,b;
    exgcd(x,mod,d,a,b);
    return (a+mod)%mod;
}
inline int C(int x,int y,int m)
{
    if(x>y) return 0; 
    int r=jc[y][m]*(int)inv(jc[x][m],p[m])%p[m]*inv(jc[y-x][m],p[m])%p[m];
    return (int)r;
}
inline int lucas(int x,int n,int m)
{
    if (n==0) return 1;
    return mul(lucas(x/p[m],n/p[m],m),C(x%p[m],n%p[m],m),p[m]);
} 
inline void calc(int x)
{
    for (int i=0;i<4;i++)   s[i]=(s[i]+lucas(x,n,i))%p[i];
}
inline int crt()
{
    int sum=0,d,x,y,mod=Mod-1;
    for (int temp,i=0;i<4;i++)
    {
        x=y=d=0;
        temp=mod/p[i];
        exgcd(p[i],temp,d,x,y);
        sum=(sum+mul(mul(temp,y,mod),s[i],mod))%mod;
    }
    sum+=mod;
    return sum==0?mod:sum; 
}
inline int ksm(int x,int y)
{
    int result=1;
    for (;y;y>>=1,x=mul(x,x,Mod))
        if(y&1) result=mul(result,x,Mod);
    return (int)result;
}
int main()
{
    int i,sq,j;
    for (i=0;i<4;i++) jc[0][i]=jc[1][i]=1;
    for (i=0;i<4;i++)   for (j=2;j<=p[i];j++)  jc[j][i]=jc[j-1][i]*j%p[i]; 
    scanf("%d%d",&n,&g);
    sq=(int)floor(sqrt(n));
    for(i=1;i<=sq;i++)   if (n%i==0){calc(i);if (i*i!=n) calc(n/i);}  
    g%=Mod;
    printf("%d\n",ksm(g,crt()));
}
← 【bzoj1294】【状压dp】围豆豆 neerc southern →
 
comments powered by Disqus