本文共 3912 字,大约阅读时间需要 13 分钟。
题意:求G^(C(N,N/K))%mod ( K|N)
10%的数据中,1 <= N <= 50;
20%的数据中,1 <= N <= 1000; 40%的数据中,1 <= N <= 100000; 100%的数据中,1 <= G <= 1000000000,1 <= N <= 1000000000。#include#include #include #include #include using namespace std;#define maxn 35620typedef long long LL;#define MOD 999911659#define M 999911658LL w[4]={2,3,4679,35617};LL a[4];LL fac[4][maxn];LL Pow(LL a,LL b,LL mod)//快速幂{ LL ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b >>= 1; } return ans;}void init()//预处理阶乘{ for(int i=0;i<4;i++) { fac[i][0]=1; for(int j=1;j<=w[i];j++) { fac[i][j]=(fac[i][j-1]*j)%w[i]; } }}/********************************* 组合数取模用费马小定理*********************************/LL C(LL n,LL m,int x)//组合数取模{ if(n < m) return 0; return (fac[x][n] * Pow((fac[x][n-m]*fac[x][m]),w[x]-2,w[x]))%w[x];}/******************************** lucas 处理大组合数取模********************************/LL Lucas(LL n,LL m,int x)//lucas定理{ if(m==0) return 1; return (Lucas(n/w[x],m/w[x],x)*C(n%w[x],m%w[x],x))%w[x];}/***************************** 扩展欧几里得求乘法逆元*****************************/LL exgcd(LL a,LL b,LL &x,LL &y)//乘法逆元{ if(!b){x = 1;y = 0;return a;} LL ans = exgcd(b,a%b,x,y); LL t = x;x = y;y = t - a/b*y; return ans;}/**************************************************************************************** 中国剩余定理:* x = b1 % m1 * x = b2 % m2* x = b3 % m3* .* gcd(m1,m2,m3,...) = 1;* M = m1 * m2 * m3 *.....;* M1 = m2 * m3 * ...., M2 = m1 * m3 * ...., M3 = m1 * m2 * m4 *....., ......;* M1 * M(-1) = 1 % M ,M2 * M2(-1) = 1 % M;* res = (M1(-1)*b1 + M2(-1)*b2+.....)%M;res即为所求值* 注:如果取模的值相同:都是m1 那么 bn的值可以相加计算;* 略屌。。。。。。。。。。。。。。******************************************************************************************/LL CRT()//计算组合数和取模之后的值{ LL i,d,x0,y0,ans=0; for(i = 0;i < 4;i++)//中国剩余定理 { d=M/w[i]; exgcd(d,w[i],x0,y0); ans=(ans+d*x0*a[i])%M; } if(ans <= 0) ans += M; return ans;}int main(){ init(); LL g,n; while(cin>>n>>g) { memset(a,0,sizeof(a)); for(int i=1;i*i<=n;i++) { if(n%i==0) { LL tmp=n/i; for(int j=0;j<4;j++) { if(tmp!=i) a[j]=(a[j]+Lucas(n,i,j))%w[j]; a[j]=(a[j]+Lucas(n,tmp,j))%w[j]; } } } cout< <
转载地址:http://ccsgi.baihongyu.com/