因为999911659是个素数
欧拉定理得
然后指数上中国剩余定理
然后分别lucas定理就好了
注意G==P的时候的特判
1 /* http://www.cnblogs.com/karl07/ */ 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define ll long long 9 10 const ll P=999911659; 11 const ll p1[5] = {0, 2, 3, 4679, 35617}; 12 const ll N=40000; 13 ll g,n,cnt=0; 14 ll fac[N+5],ifac[N+5]; 15 ll p[N],ans[5]; 16 17 ll Q_pow(ll a,ll b,ll p){ 18 ll ans=1; 19 while (b){ 20 if (b&1) ans=ans*a%p; 21 a=a*a%p; 22 b=(b>>1); 23 } 24 return ans; 25 } 26 27 void FAC(ll p){ 28 ifac[0]=fac[0]=1; 29 for (int i=1;i<=N;i++) fac[i]=fac[i-1]*i%p,ifac[i]=Q_pow(fac[i],p-2,p); 30 } 31 32 ll C(ll n,ll m,ll p){ 33 if (m>n) return 0; 34 return fac[n]*ifac[m]%p*ifac[n-m]%p; 35 } 36 37 ll lucas(ll n,ll m,ll p){ 38 if (m==0) return 1; 39 return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p; 40 } 41 42 void fj(ll x){ 43 for (int i=1;i*i<=x;i++){ 44 if (x%i==0){ 45 p[++cnt]=i; 46 if (i*i!=x) p[++cnt]=n/i; 47 } 48 } 49 } 50 51 ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;} 52 53 void ex_gcd(ll a,ll b,ll &x,ll &y){ 54 if (b==0){x=1;y=0;return;} 55 ex_gcd(b,a%b,y,x); 56 y-=x*(a/b); 57 } 58 59 60 ll China(){ 61 ll a0=ans[1],p0=p1[1]; 62 for (int i=2;i<=4;i++){ 63 ll x,y,g=gcd(p0,p1[i]); 64 ex_gcd(p0,p1[i],x,y); 65 x=(x*(ans[i]-a0)%p1[i]+p1[i])%p1[i]; 66 a0=a0+x*p0; 67 p0=p0/g*p1[i]; 68 } 69 return a0; 70 } 71 72 void work(){ 73 for(int i=1;i<=4;i++){ 74 FAC(p1[i]); 75 for (int j=1;j<=cnt;j++){ 76 ans[i]=(ans[i]+lucas(n,n/p[j],p1[i]))%p1[i]; 77 } 78 } 79 printf("%lld ",Q_pow(g,China(),P)); 80 } 81 82 int main(){ 83 scanf("%lld%lld",&n,&g); 84 if (g==P) {puts("0"); return 0;} 85 fj(n); 86 work(); 87 return 0; 88 } 89
各种zz的错误。。调了一年
而且跑的巨慢无比。。