标签：P2155 le 洛谷 limits int dfrac 1e7 SDOI2008

P2155 [SDOI2008] 沙拉公主的困惑

题目
题面非常的简洁，求 \(\sum\limits_{i=1}^{n!}[i\perp m!]\)
直接颓式子，

\[\begin{aligned} ans&=\dfrac{n!}{m!}\cdot\varphi(m!)\\\\ &=\dfrac{n!}{m!}*m!\prod\limits_{p\mid m!}[\dfrac{p-1}{p}]\\ &=n!\cdot\dfrac{\prod\limits_{p\in\mathbb{P},p\le m}(p-1)}{\prod\limits_{p\in\mathbb{P},p\le m}p} \end{aligned} \]

p为1到m中的所有质数，逆元和阶乘预处理直接乘起来就行。
小粉兔提出模数可能会小于n，
当 \(mod\le m\le n\) 时，逆元遇到 \(p\mid i\) 时，\(inv_i=1\) ，然后阶乘时要判断，因为分子和分母可以消去 p 。
而当 \(m<mod\le n\) 时，即不能消去 p 时就直接输出0 。
感觉这道题有点毒瘤。
代码如下

#include<bits/stdc++.h>

#define int long long

using namespace std;

int prime[(int)(1e6)+5],

ny[(int)(1e7)+5],num[(int)(1e7)+5],

x,y,cj[(int)(1e6)+5];

int jie[(int)(1e7)+5];

bool vis[(int)(1e7)+5];

void getprime(int n){

    int m=0;

    for(int i=2;i<=n;i++){

        if(!vis[i])prime[++m]=i;num[i]=m;

        for(int j=1;j<=m&&prime[j]*i<=n;++j){

            vis[prime[j]*i]=1;

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

        }

    }

}

int read(){

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

    return x*f;

}

void write(int x){

    if(x<0)putchar('-'),x=-x;

    if(x>9)write(x/10);

    putchar(x%10+48);

}

main(){

    int t,p,n,m;t=read();p=read();ny[0]=ny[1]=1;getprime((int)(1e7)+2);

    for(int i=2;i<=1e7;++i){ny[i]=(p-p/i)*ny[p%i]%p;}

    jie[1]=1;cj[0]=1;

    for(int i=2;i<=(int)(1e7)+1;++i)

        if(i==p)

            jie[i]=jie[i-1];

        else

            {jie[i]=i*jie[i-1]%p;}

    for(int i=1;i<=num[(int)1e7];++i){cj[i]=(prime[i]-1)*cj[i-1]%p*ny[prime[i]%p]%p;}

    while(t--){

        n=read(),m=read();

        if(n>=p&&m<p)

        {

            puts("0");

            continue;

        }

        n=jie[n];int pre=num[m];

        write(n*cj[pre]%p);

        putchar('\n');

    }

    return 0;

}

/*

1 3

4 3

*/

另外可以优化，只处理 \(max(n)\) 即可。最优解就是这么卡的。

标签：P2155,le,洛谷,limits,int,dfrac,1e7,SDOI2008
From： https://www.cnblogs.com/Ishar-zdl/p/17737035.html