质数--luogu2155沙拉公主的困惑

本文主要是介绍质数--luogu2155沙拉公主的困惑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

啊不带了写题解了
放个很好的链接
www.cnblogs.com/yangyaojia

然后贴代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 10000005
using namespace std;
int t,mod,n[maxn],m[maxn],mn,mm,ans;
int inv[maxn],k[maxn],f1[maxn],f2[maxn];
bool vis[maxn];inline int rd(){int x=0,f=1; char c=' ';while(c>'9' || c<'0') {if(c=='-') f=-1; c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0', c=getchar();return x*f;
}inline void work(){inv[1]=1,k[1]=1,f1[1]=1,f2[1]=1;for(int i=2;i<=sqrt(mm);i++)if(!vis[i])for(int j=2;j<=mn/i;j++) vis[i*j]=1;for(int i=2;i<=mn;i++){if(i<=mm){inv[i]=(1LL*(mod-mod/i)*inv[mod%i])%mod;}if(i<=mm){if(!vis[i]){f1[i]=(1LL*f1[i-1]*((i-1)%mod))%mod;f2[i]=(1LL*f2[i-1]*inv[i])%mod;}else{f1[i]=f1[i-1];f2[i]=f2[i-1];  }}k[i]=(1LL*k[i-1]*(i%mod))%mod;}
}int main(){t=rd(); mod=rd();for(int i=1;i<=t;i++){n[i]=rd(); m[i]=rd();mn=max(mn,n[i]); mm=max(mm,m[i]);}work();for(int i=1;i<=t;i++){ans=(((1LL*k[n[i]]%mod)*1LL*(f1[m[i]]%mod)%mod)*1LL*(f2[m[i]]%mod))%mod;printf("%d\n",ans);}return 0;
}

这篇关于质数--luogu2155沙拉公主的困惑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---