bzoj2186: [Sdoi2008]沙拉公主的困惑 逆元

传送门

题意：求1-n!中与m!互质的数的个数，其中m小于n。

思路：由于m小于n，所以n!一定是m!的倍数，小于m!与m!互质的数的个数为phi(m!)，所以1-n!中与m!互质的数的个数为n!/m!*phi(m!)=n!/m!*m!*(1-1/p1)*(1-1/p2)*...(1-1/pk) =n!(1-1/p1)*(1-1/p2)*...(1-1/pk)其中p1-pk是m!的素因子，其实也就是小于m的所有素数，最后结果再对一个素数取余。

这个题时间卡的确实很紧，在求逆元的时候用的是o(p)复杂度来求：

void init()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(i>=mod) break;
        inv[i]=((mod-mod/i)*inv[mod%i])%mod;
    }
}

而且在求 (1-1/p1)*(1-1/p2)*...(1-1/pk)时先预处理，否则也是超时

完整代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1e7+5;
bool prime[maxn];
int cnt;
int mod;
ll inv[maxn];
ll jc[maxn];
ll res[maxn];
void isprime()
{
    prime[0]=false;
    prime[1]=false;
    prime[2]=true;
    for(int i=3;i<maxn;i+=2)
    {
        prime[i]=true;
        prime[i+1]=false;
    }
    for(int i=3;i<=sqrt((double)maxn);i+=2)
        if(prime[i])
            for(int j=i+i;j<maxn;j+=i)
                prime[j]=false;
}
void init()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(i>=mod) break;
        inv[i]=((mod-mod/i)*inv[mod%i])%mod;
    }
}
void factorial()
{
    jc[0]=jc[1]=1;
    for(int i=2;i<maxn;i++)
    {
        jc[i]=jc[i-1]*i%mod;
    }
}
int main()
{
    int t;
    scanf("%d%d",&t,&mod);
    isprime();
    init();
    factorial();

    res[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(prime[i])
        {
            res[i]=res[i-1]*(i-1)%mod;
            res[i]=res[i]*inv[i%mod]%mod;
        }
        else
            res[i]=res[i-1];
    }

    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        ll ans=jc[n]*res[m]%mod;
        printf("%lld\n",ans);
    }
    return 0;
}