首页 > 代码库 > BZOJ 2186 [Sdoi2008]沙拉公主的困惑

BZOJ 2186 [Sdoi2008]沙拉公主的困惑

数论重学篇.

首先需要看出答案是:

  n!/m!*phi(m!)

  小于m!的数中与m!互质的数有phi(m!)个,由辗转相除法可知,

  gcd(x,m!)=1 <==>  gcd(x+m!,m!)=1

  然后直接算就行了.

技术分享
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define FILE "dealing"
 5 #define up(i,j,n) for(int i=j;i<=n;i++)
 6 #define db long double 
 7 #define pii pair<int,int>
 8 #define pb push_back
 9 #define mem(a,L) memset(a,0,sizeof(int)*(L+1))
10 template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
11 template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
12 template<class T> inline T squ(T a){return a*a;}
13 const ll maxn=10000100+10,inf=1e9+10,limit=1e7;
14 ll read(){
15     ll x=0,f=1,ch=getchar();
16     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
17     while(ch>=0&&ch<=9)x=(x<<1)+(x<<3)+ch-0,ch=getchar();
18     return x*f;
19 }
20 int T,mod;
21 int fac[maxn],inv[maxn],f[maxn];
22 int prime[maxn],tail;
23 bool b[maxn];
24 int main(){
25     freopen(FILE".in","r",stdin);
26     freopen(FILE".out","w",stdout);
27     T=read();mod=read();
28     fac[0]=1;up(i,1,limit)fac[i]=(ll)fac[i-1]*i%mod;
29     inv[0]=inv[1]=1;up(i,2,limit)inv[i]=(mod-(ll)inv[mod%i]*(mod/i)%mod)%mod;
30     f[1]=1;
31     for(int i=2;i<=limit;i++){
32         if(!b[i])prime[++tail]=i,f[i]=(ll)f[i-1]*(i-1)%mod*inv[i]%mod;
33         else f[i]=f[i-1];
34         for(int j=1;j<=tail&&prime[j]*i<=limit;j++){
35             b[i*prime[j]]=1;
36             if(i%prime[j]==0)break;
37         }
38     }
39     while(T--){
40         int n=read(),m=read();
41         printf("%lld\n",(ll)fac[n]*f[m]%mod);
42     }
43     return 0;
44 }
View Code

 

BZOJ 2186 [Sdoi2008]沙拉公主的困惑