P2155 [SDOI2008]沙拉公主的困惑

题目描述

大富翁国因为通货膨胀，以及假钞泛滥，*决定推出一项新的政策：现有钞票编号范围为\(1\)到\(N\)的阶乘，但是，*只发行编号与\(M!\)互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对\(R\)取模后的答案即可。\(R\)是一个质数。

输入输出格式

输入格式：

第一行为两个整数\(T\)，\(R\)。\(R \le 10^9+10\)，\(T \le 10000\)，表示该组中测试数据数目，\(R\)为模。

后面\(T\)行，每行一对整数\(N\)，\(M\)，见题目描述\(m \le n\)

输出格式：

共\(T\)行，对于每一对\(N\)，\(M\)，输出\(1\)至\(N!\)中与\(M!\)素质的数的数量对\(R\)取模后的值

---

题意：

求\(\frac{N!}{M!} \varphi(M!)\)

注意，这里每\(M!\)段互质的个数是一样的，可以用\(gcd(a,b)=gcd(b,a-b)\)证明，而\(M!|N!\)，才有了上面一个式子

按照欧拉函数定义式化简一下

\(N!\prod_{p|m!}\frac{p-1}{p}\),\(p\)质数

很明显把两个乘积项预处理一下，右边可以二分找一下

注意预处理阶乘时不能简单的预处理，因为如果\(R \le N\),那么就输出\(0\)了，事实上不一定输出\(0\)

先把\(R\)的次数拿出来，然后再搞一搞

是不是感觉这样是\(O(NlogR)\)的？事实上不是

这个和\(N!\)中\(R\)的次数直接相关，设\(f(n)\)代表\(n!\)中有多少个因子\(r\)

显然有\(f(n)=f(\lfloor \frac{n}{r} \rfloor)+\lfloor \frac{n}{r} \rfloor\)

结果是\(O(n)\)的

事实上跑上去有点慢。。

---

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

const int N=1e7;

const int M=7e5;

bool ispri[N+10];

int pri[M],cnt,fr[M],num[M],fac[N+10],numfac[N+10],r,t,n,m;

int mul(int a,int b)

{

    ll c=(ll)(a)*b%r;

    return (int)(c);

}

int inv(int b,int k)

{

    int f=1;

    while(k)

    {

        if(k&1) f=mul(f,b);

        b=mul(b,b);

        k>>=1;

    }

    return f;

}

void init()

{

    memset(ispri,true,sizeof(ispri));

    for(int i=2;i<=N;i++)

    {

        if(ispri[i])

            pri[++cnt]=i;

        for(int j=1;j<=cnt&&pri[j]*i<=N;j++)

        {

            ispri[pri[j]*i]=false;

            if(i%pri[j]==0) break;

        }

    }

    fr[0]=1;

    for(int i=1;i<=cnt;i++)

    {

        num[i]=num[i-1];

        fr[i]=fr[i-1];

        if(pri[i]-1==r)

            ++num[i],fr[i]=mul(fr[i],inv(pri[i],r-2));

        else if(pri[i]==r)

            --num[i],fr[i]=mul(fr[i],pri[i]-1);

        else

            fr[i]=mul(fr[i],mul(inv(pri[i],r-2),pri[i]-1));

    }

    fac[0]=1;

    for(int i=1;i<=N;i++)

    {

        fac[i]=fac[i-1];

        numfac[i]=numfac[i-1];

        int d=i;

        while(d%r==0) ++numfac[i],d/=r;

        fac[i]=mul(fac[i],d);

    }

}

int main()

{

    scanf("%d%d",&t,&r);

    init();

    while(t--)

    {

        scanf("%d%d",&n,&m);

        int pos=std::upper_bound(pri+1,pri+1+cnt,m)-pri-1;

        int ans=mul(fac[n],fr[pos]);

        if(num[pos]+numfac[n]==0) printf("%d\n",ans);

        else printf("0\n");

    }

    return 0;

}

---

2018.9.27