洛谷 P2155 BZOJ 2186 codevs 2301 [SDOI2008]沙拉公主的困惑

題目描述

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

輸入輸出格式

輸入格式：

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

輸出格式：

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

輸入輸出樣例

輸入樣例#1：

1 11
4 2      

輸出樣例#1：

1

資料範圍：
對于100%的資料，1 < = N , M < = 10000000      

解題思路

　　

http://www.cnblogs.com/yangyaojia/p/6434611.html

、

http://blog.csdn.net/loi_dqs/article/details/50520309

吐槽

　　這題一題能抵三題做了。

　　不想被卡常就離線吧，篩法篩到最大的n即可，否則卡常、卡記憶體太嚴重了，我的好不容易洛谷ac，跑了6s。

　　求逆元可以

線性遞推

，也可以擴歐。

popoqqq大神部落格的代碼

(https://www.luogu.org/record/show?rid=2565704)、

黃學長部落格

(https://www.luogu.org/record/show?rid=2565713)裡線性遞推逆元的代碼都在洛谷爆零，不知為啥。

　　我的代碼離線int會溢出，估計是篩法出問題，還不夠優化，于是遞推求逆元的數組開不下了，就用擴歐吧。

　　卡一波常1.3s跑完(BZOJ不開O2跑了2.9s)。

源代碼

6s的，求逆元用線性遞推(BZOJ TLE)

#include<cstdio>
#include<cstring>
#include<algorithm>
int T,R,n,m;
long long  jc[10000010]={0};//階乘取模
long long inv[10000010]={0};//逆元
bool not_prime[10000010]={0};//篩子
long long ans[10000010]={0};//pi累乘

void init()
{
    inv[1]=1;
    for(int i=2;i<=10000000&&i<R;i++)
        inv[i]=(R-R/i)%R*inv[R%i]%R;
    ans[1]=1;jc[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        jc[i]=jc[i-1]*i%R;
        if(!not_prime[i])
        {
            ans[i]=ans[i-1]*(i-1)%R*inv[i%R]%R;
            for(int j=i<<1;j<=10000000;j+=i)
                not_prime[j]=1;
        }
        else
            ans[i]=ans[i-1];
    }
}

int main()
{
    scanf("%d%d",&T,&R);
    init();
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",(long long)(jc[n])*(long long)(ans[m])%R);
    }
    return 0;
}      

1.3s的，求逆元用擴歐

#include<cstdio>
#include<algorithm>
int T,R,maxn=-1;
long long  jc[10000010]={0};//階乘取模
//int inv[10000010]={0};//逆元
bool not_prime[10000010]={0};//篩子
long long ans[10000010]={0};//pi累乘
int n[10000010]={0},m[10000010]={0};


void exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
}
inline int getine(int t)
{
    int x,y;
    exgcd(t,R,x,y);
    return (x%R+R)%R;
}//擴歐求逆元

inline void Read(int &in){
    static char ch;
    for(ch=getchar();ch>'9'||ch<'0';ch=getchar()) ;
    for(in=0;ch>='0'&&ch<='9';ch=getchar()) in=in*10+ch-'0';
}
void init()
{
    /*inv[1]=1;
    for(int i=2;i<=maxn&&i<R;i++)
        inv[i]=(R-R/i)%R*inv[R%i]%R;*///線性遞推求逆元
    ans[1]=1;jc[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        jc[i]=jc[i-1]*i%R;
        if(!not_prime[i])
        {
            ans[i]=ans[i-1]*(i-1)%R*getine(i%R)%R;
            for(int j=i<<1;j<=maxn;j+=i)
                not_prime[j]=1;
        }
        else
            ans[i]=ans[i-1];
    }
}

int main()
{
    Read(T);Read(R);
    for(register int i=1;i<=T;i++)
         Read(n[i]),Read(m[i]),maxn=std::max(maxn,n[i]);
    init();
    for(register int i=1;i<=T;i++)
        printf("%lld\n",jc[n[i]]*ans[m[i]]%R);
    return 0;
}      

洛谷記錄裡最優的代碼，使用者ID小小莫。Orz，洛谷跑了0.9s，BZOJ不開O2跑了2.6s，素數篩法值得學習。

#include <cstdio>
#include <algorithm>
using namespace std;
static const int maxm = 10000 + 50;
static const int maxx = 10000000 + 50;
typedef long long LL;
bool Notprime[maxx];
int inv[maxx],phi[maxx],fac[maxx],prime[maxx];
int T,n[maxm],m[maxm],p,cnt,tot;

void Read(int &);

inline void Linear_shaker(){
    int maxn = tot+1;
    fac[1]=1;inv[1]=1;phi[1]=1;
    for(register int i=2;i<maxn;i++){
        if(!Notprime[i])
            prime[++cnt]=i;
        for(register int j=1;j<=cnt && i*prime[j]<maxn;j++){
            Notprime[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    for(register int i=2;i<=maxn;i++){
        fac[i] = ((LL)fac[i-1]*i)%p;
        if(i<p) inv[i] = (LL)(p-p/i)*inv[p%i]%p;
        if(!Notprime[i]) phi[i] = (LL)phi[i-1]*(i-1)%p*inv[i%p]%p;
        else phi[i] = phi[i-1];
    }
}
int main(){
    Read(T),Read(p);
    for(register int i=1;i<=T;i++) Read(n[i]),Read(m[i]),tot = max(tot,n[i]);
    Linear_shaker();
    for(register int i=1;i<=T;i++)
        printf("%lld\n",(LL)fac[n[i]]*phi[m[i]]%p);
    return 0;
}

void Read(int &in){
    static char ch;
    for(ch=getchar();ch>'9'||ch<'0';ch=getchar()) ;
    for(in=0;ch>='0'&&ch<='9';ch=getchar()) in=in*10+ch-'0';
}