题意：计算
从外往里分析:
0. p=999911659是素数.所以先判断G%p是否为0的情况,不为0说明gcd(G,p)=1 接着往下走
1.互质则使用欧拉函数对这个幂次进行降幂.即，但是这儿对大组合数的和取的模不是质数,所以要借用ExLucass的思想,不过这儿不能用这个扩展的卢卡斯,它的复杂度远比卢卡斯定理的复杂度高出很多.
2.lucass:把(合数)模数分解质因子pi，每个pi下的 算出.对应的所有的pi算完之后,用crt解同余方程就合并出了G的幂次，用快速幂搞一下就行了.
#include <bits/stdc++.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
#pragma comment(linker, "/STACK:1024000000,1024000000")
void ex_gcd(int a, int b, int &d, int &x, int &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a,int b){return a/gcd(a,b)*b;}//只适用于a,b 2者的情况
int inv_exgcd(int a, int m) { int d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; }
typedef long long ll;
const int maxn=1e6;
using namespace std;
ll fac[maxn];
ll a,b,Mod=999911659,mod;
int r[5];
int primer[]={2,3,4679,35617};
ll Pow(ll a,ll n,ll mod)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
void init()
{fac[0]=1;for(int i=1;i<=mod;++i)fac[i]=fac[i-1]*i%mod;
}
ll C(ll n,ll m,ll mod)
{if(m>n)return 0;ll ans=fac[n];ans*=inv_exgcd((fac[m]*fac[n-m])%mod,mod);return ans%mod;
}
ll Lucas(ll n,ll m,ll mod)
{if(m==0)return 1;return C(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)%mod;
}
ll crt(int n,int *c,int *m){ll M=1,ans=0;for(int i=0;i<n;++i) M*=m[i];
for(int i=0;i<n;++i) ans=(ans+M/m[i]*c[i] %M *inv_exgcd(M/m[i],m[i]))%M; return ans;}
void solve(ll n,ll G)
{memset(r,0,sizeof(r));for(int k=0;k<4;++k){mod=primer[k],init();for(ll i=1;i*i<=n;++i)///暴力求解，不知道有没有O(1)的公式去求出{if(n%i==0){r[k]=(r[k]+Lucas(n,i,primer[k]))%primer[k];if(i*i!=n)r[k]=(r[k]+Lucas(n,n/i,primer[k]))%primer[k];}}}// r数组就是所得的余数, primer为模数,用crt合并解出最终的结果 ll ans=crt(4,r,primer);ans=Pow(G,ans,Mod);printf("%lld\n",ans);
}
int main()
{ll G,n;while(scanf("%lld%lld",&n,&G)!=EOF){if(G%Mod==0){printf("0\n");continue;}G%=Mod;solve(n,G);}return 0;
}
虽说改出来的2个T到飞，也是改出来的啊:
杀鸡不是不可以用宰牛刀,可是你想过鸡的感受嘛><
#include <iostream>//Lucas模板
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
const int maxn=1e5;
const int MOD=999911658;
using namespace std;
void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a,int b){return a/gcd(a,b)*b;}//Ïȳýºó³Ë·ÀÒç³ö
ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; }
ll cnt=0;
int primer[5]={2,3,4679,35617};
ll A[5];
ll Pow(ll a,ll n,ll mod)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
ll C(ll n,ll p,ll pk)
{if(n==0)return 1;ll ans=1;for(ll i=2;i<=pk;++i)if(i%p)ans=ans*i%pk;ans=Pow(ans,n/pk,pk);for(ll k=n%pk,i=2;i<=k;++i)if(i%p)ans=ans*i%pk;return ans*C(n/p,p,pk)%pk;
}
ll ex_lucas(ll n,ll m,ll p,ll pi,ll pk)
{ll i,j,k=0,a,b,c,ans;a=C(n,pi,pk),b=C(m,pi,pk),c=C(n-m,pi,pk);for(i=n;i;i/=pi)k+=i/pi;for(i=m;i;i/=pi)k-=i/pi;for(i=n-m;i;i/=pi)k-=i/pi;ans=a*inv_exgcd(b,pk)%pk*inv_exgcd(c,pk)%pk*Pow(pi,k,pk)%pk;return ans*(p/pk)%p*inv_exgcd(p/pk,pk)%p;中国剩余定理 a[i]*M*x 余数*其他个个素数的乘积*x
}
void solve(ll G,ll n)
{if(G%(MOD+1)==0){printf("0\n");return;}G%=MOD+1;ll ans=0;for(int i=0;i<4;++i){for(ll j=1;j*j<=n;++j){if(n%j==0){ans=(ans+ex_lucas(n,j,MOD,primer[i],primer[i]))%MOD;if(j*j!=n)ans=(ans+ex_lucas(n,n/j,MOD,primer[i],primer[i]))%MOD;}}}ans%=MOD;ans=Pow(G,ans,MOD+1);printf("%lld\n",ans);
}
int main()
{//IO;ll n,G;scanf("%lld%lld",&n,&G);//cin>>n>>G;solve(G,n);return 0;
}
总结
以上是生活随笔为你收集整理的HYSBZ-1951 古代猪文 【好题】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
