Time Limit:?10 Sec??Memory Limit:?259 MB
Submit:?2463??Solved:?820
[Submit][Status][Discuss]

Description

　　大富翁國因為通貨膨脹，以及假鈔泛濫，政府決定推出一項新的政策：現有鈔票編號范圍為1到N的階乘，但是，政府只發行編號與M!互質的鈔票。房地產第一大戶沙拉公主決定預測一下大富翁國現在所有真鈔票的數量。現在，請你幫助沙拉公主解決這個問題，由于可能張數非常大，你只需計算出對R取模后的答案即可。R是一個質數。

Input

第一行為兩個整數T，R。R<=10^9+10，T<=10000，表示該組中測試數據數目，R為模后面T行，每行一對整數N，M，見題目描述 m<=n

Output

共T行，對于每一對N，M，輸出1至N！中與M！素質的數的數量對R取模后的值

Sample Input

1 11
4 2

Sample Output

1
數據范圍：
對于100%的數據，1 < = N , M < = 10000000
題解： 　　這題要求在(1,N!)里與M!互質的數的個數，由于N!>M!，所以答案分成兩部分，一部分是用歐拉函數phi(M!),表示1~M!里與M!互質的數的個數，還有一部分是(M!+1,N!)里的一部分數也有可能和M!互質。但是這部分數字比較難處理，現在由輾轉相除法的原理可知：如果gcd(x,M!)==1，則一定有gcd(x+M!,M!)==1，所以(M!+1,N!)里的和M!互質的數一定是x+kM! (k∈Z)。所以答案就是：phi(M!)*(N!/M!)%R 　　現在的問題就是N!，M!都很大，如何求上面的式子。我們讓N!%R單獨算，把phi(M!)/(M!)放在一起，令f(M)=phi(M!)/M!，根據phi(x)=x*(1-1/p1)*(1-1/p2)*…*(1-1/pk) ，可以上下同時消掉M!，f(m)=(p1-1)/p1*(p2-1)/p2*…其中pi為不大于M的質數(因為由歐拉函數知pi是素因子，而M!=1*2*3*4***M，所以小于M的素數就是素因子)，所以對于f(i)，如果i是質數f(i)=f(i-1)*(i-1)/i，否則f(i)=f(i-1)。 　　還有一個問題，就是f(i)=f(i-1)*(i-1)/i 在模R意義下存在除法，這就有可能出現分數，這就需要用到乘法逆元，把除法轉化成乘法。具體講解：乘法逆元?用擴展歐幾里得求解乘法逆元

　　根據以上關系式可以預處理f(1)~f(10^7)。每次詢問只需要輸出f(M)*N!%R即可。

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=1e7+5; 5 int N,M,P,T; 6 LL fac[maxn],ans[maxn]; 7 bool f[maxn]; 8 inline void exgcd(int a,int b,int &x,int &y){ 9 if(b==0){ 10 x=1; y=0; 11 return ; 12 } 13 exgcd(b,a%b,x,y); 14 int t=x; 15 x=y; y=t-a/b*x; 16 } 17 inline int getinv(int a){ 18 int x=0,y=0; 19 exgcd(a,P,x,y); 20 return (x%P+P)%P; 21 } 22 int main(){ 23 scanf("%d%d",&T,&P); 24 fac[1]=1; 25 for(int i=2;i<=1e7;i++) fac[i]=fac[i-1]*i%P;//預處理 N!%R 26 ans[1]=1; 27 for(int i=2;i<=1e7;i++){ 28 if(f[i]==false){// 是素數 29 ans[i]=ans[i-1]*(i-1)%P*getinv(i)%P; 30 for(int j=2;j<=1e7/i;j++) f[i*j]=true;//篩素數 31 } 32 else ans[i]=ans[i-1]; 33 } 34 while(T--){ 35 scanf("%d%d",&N,&M); 36 printf("%lld\n",ans[M]*fac[N]%P); 37 } 38 return 0; 39 }

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/5222291.html

總結

以上是生活随笔為你收集整理的bzoj 2186: [Sdoi2008]沙拉公主的困惑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。