网站建设与管理单招,软件推广网站,做一个小说阅读网站怎么做,课堂阵地建设网站传送门 文章目录题目描述解析总结代码题目描述 解析
简单来说#xff0c;就是求#xff1a; g∑C(d,n)(d是n的约数#xff09;mod 999911659 可以先特判一下#xff0c;999911659|g时#xff0c;答案为0 否则#xff0c;可以通过欧拉定理转化为#xff1a; g∑C(d,n)(d…传送门
文章目录题目描述解析总结代码题目描述 解析
简单来说就是求 g∑C(d,n)(d是n的约数mod 999911659 可以先特判一下999911659|g时答案为0 否则可以通过欧拉定理转化为 g∑C(d,n)(d是n的约数mod999911658 mod 999911659 取完模之后指数已经限制在了一个较小的范围如果求出其值就可以用快速幂解决 现在考虑求这个指数 ∑C(d,n)(d是n的约数mod999911658 面对这样较大的组合数取模容易想到用卢卡斯定理解决 但是问题在于本题的模数太大 所以我们考虑对这个模数进行质因数分解 999911658234679*35617 如果对这四个模数分别取模就能把模数限制在一个可以接受的大小并建立出4个同余方程 然后再利用中国剩余定理解出这个指数即可
总结
本题的关键在于遇见大模数后进行质因数分解在进行中国剩余定理的转化
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
#define ll long long
#define int long long
const int N3e5100;
const ll mod999911658;
const ll Mod999911659;
ll ksm(ll x,ll o){ll ans1,resx%Mod;while(o){if(o1) ans(ans*res)%Mod;res(res*res)%Mod;o1;}return ans%Mod;
}
ll n;
ll g;
ll m[5]{0,2,3,4679,35617},M[5],MM,t[5];
ll d[N],num;
void divide(ll x){int topfloor(sqrt(x));d[num]1;for(int i2;itop;i){if(x%i0){d[num]i;if(n/i!i) d[num]n/i;}}d[num]x;return;
}
ll ni[5][N],jc[N];
ll a[5];ll C(int k,ll d,ll n){if(dn) return 0;if(dn) return 1;return (jc[n]*ni[k][d]*ni[k][n-d])%m[k];
}
ll lucas(int k,ll d,ll n){if(dn) return 1;if(dn) return 0;return (C(k,d%m[k],n%m[k])%m[k])*lucas(k,d/m[k],n/m[k])%m[k];
}
void gcd(ll a,ll b,ll x,ll y){if(b0){x1;y0;return;}gcd(b,a%b,x,y);int oy;yx-a/b*y;xo;y%mod;x%mod;
}
signed main(){scanf(%lld%lld,n,g);if(g%Mod0) {printf(0);return 0;}divide(n);jc[0]jc[1]1;for(int i1;i4;i) ni[i][0]ni[i][1]1;for(int i2;i35167;i){jc[i](jc[i-1]*i)%mod;for(int j1;j4;j) ni[j][i]((m[j]-m[j]/i)*ni[j][m[j]%i])%m[j];}for(int i2;i35167;i) for(int j1;j4;j)ni[j][i](ni[j][i]*ni[j][i-1])%m[j];for(int i1;inum;i){for(int j1;j4;j){a[j](a[j]lucas(j,d[i],n))%m[j];//printf(d%lld mod%lld ans%lld\n,d[i],m[j],lucas(j,d[i],n)%m[j]);}}MMmod;ll ans0;for(int i1;i4;i){M[i]MM/m[i];ll o;gcd(M[i],m[i],t[i],o);ans(t[i]*M[i]*a[i])%mod;ans%mod;}
// for(int j1;j4;j){
// printf(k%d mod%d:\n,j,m[j]){
// for(int i1;inum;i){
// printf
// }
// }
// }ans%MM;while(ans0) ansMM;printf(%lld\n,ksm(g,ans)%Mod);return 0;
}
/*
4
5 1
5 2
7 3
4 2
*/
