BZOJ2186 [SDOI2008]沙拉公主的困惑

2014.12.22 12:42 Mon| 0 visits oi_2015| 2015_刷题日常| Text

Solution

一道优(sang)美(bing)的数学题。

欧几里得定理告诉我们,如果 $\gcd(m,n)=1$ ,那么 $\gcd(m+kn,n)=1$ 。这样,可以得到 ${n!\over m!}\times \phi(m!)$ 即为所求。整理上式,即 $n!\times {\phi(m!)\over m!}$ ,其中后半部分根据公式化简并约分,得 ${p-1\over p}\qquad(p是m的素因数)$ ,即可线性求出。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 10000000

bool v[N+5];
int t,mod,n,m,p[N+5],tot,ans[N+5],fac[N+5],inv[N+5];

void getfac(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=(long long)fac[i-1]*i%mod;
}

void getprime(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(!v[i]) p[++tot]=i;
        for(int j=1;i*p[j]<=x;j++)
        {
            v[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

void getinv(int x)
{
    inv[1]=1;
    for(int i=2;i<=x;i++)
        inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;
}

inline long long read()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    t=read(); mod=read();
    getfac(N);
    getprime(N);
    getinv(N);
    ans[1]=1;
    for(int i=2;i<=N;i++)
        if(!v[i])
            ans[i]=(long long)ans[i-1]*(i-1)%mod*inv[i%mod]%mod;
        else ans[i]=ans[i-1];
    while(t--) printf("%lld\n",(long long)fac[read()]*ans[read()]%mod);
}