[BZOJ 1951][Sdoi2010]古代猪文：Lucas定理|中国剩余定理|费马小定理|扩展欧几里得

本文主要是介绍[BZOJ 1951][Sdoi2010]古代猪文：Lucas定理|中国剩余定理|费马小定理|扩展欧几里得，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

一道综合了各种数论的神题。其实不难，主要是需要组合在一起运用。
1.费马小定理：求G^P时使用，因为G^(mod-1)%mod=1，所以需要P%=mod-1
2.Lucas定理&中国剩余定理：计算组合数取模时使用，但是本题中mod-1不为素数，因此需要结合中国剩余定理使用（即扩展Lucas定理）
3.扩展欧几里得：中国剩余定理要求逆元

/*
User:Small
Language:C++
Problem No.:1951
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const ll mod=999911659;
ll n,g,prime[5]={0,2,3,4679,35617},a[5];
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
ll crt(ll a[],ll m[],int n){ll M=1,res=0;for(int i=1;i<=n;i++) M*=m[i];for(int i=1;i<=n;i++){ll Mi=M/m[i],x,y;exgcd(Mi,m[i],x,y);res=(res+a[i]*Mi*x)%M;}return (res%M+M)%M;
}
ll pow(ll a,ll b,ll p){ll res=1;while(b){if(b&1LL) res=res*a%p;a=a*a%p;b>>=1LL;}return res;
}
ll c(ll n,ll m,ll p){if(n<m) return 0;if(n==m) return 1;if(m>n-m) m=n-m;ll res,cn,cm;res=cn=cm=1;for(int i=0;i<m;i++){cn=cn*(n-i)%p;cm=cm*(m-i)%p;}res=cn*pow(cm,p-2,p)%p;return res;
}
ll lucas(ll n,ll m,ll p){ll ans=1;while(n&&m&&ans){ans=ans*c(n%p,m%p,p)%p;n/=p;m/=p;}return ans;
}
ll cal(ll n){for(ll i=1;i*i<=n;i++){if(n%i==0){ll tmp=n/i;for(int j=1;j<=4;j++){if(tmp!=i) a[j]=(a[j]+lucas(n,tmp,prime[j]))%prime[j];a[j]=(a[j]+lucas(n,i,prime[j]))%prime[j];}}}return crt(a,prime,4);
}
int main(){freopen("data.in","r",stdin);//scanf("%lld%lld",&n,&g);if(g==mod) printf("0\n");else printf("%lld\n",pow(g,cal(n),mod)); return 0;
}