题解 luoguP2155 【[SDOI2008]沙拉公主的困惑】

这题真喵喵的毒瘤，写的时候被时空双卡。

为了发泄愤怒，我来水一篇题解

题意：求 $1-n!$1−n! 中与 $m!$m! 互质的数的个数 $(m\&lt;=n)$(m<=n)

我们发现小于 $m!$m! 的数中，与 $m!$m! 互质的数有 $\phi (m!)$φ(m!)个，那如何求大于 $m!$m! 的数中与 $m!$m! 互质的数的个数呢？

引理：若 $a,b$a,b互质，则 $a+b\times k$a+b×k与 $b$b互质。

证明：当 $gcd(a,b)=1$gcd(a,b)=1时， $gcd(b,a\%b)=1$gcd(b,a%b)=1

$\because a\%b=a-b\times k$∵a%b=a−b×k

$\therefore gcd(b,a-b\times k)=1$∴gcd(b,a−b×k)=1

得证。

那么对于一个小于 $m!$m! 且与 $m!$m! 互质的数 $x$x， $x+1\times m!$x+1×m!， $x+2\times m!$x+2×m! …都与 $m!$m! 互质。

因为 $n\&gt;=m$n>=m，所以 $n!$n!是 $m!$m!的倍数，那么 $1-n!$1−n! 中与 $m!$m! 互质的数的个数，根据上面的结论，很显然就是：

$res=\phi (m!)\times \frac{n!}{m!}=m!\times \prod _{i=1}^k\left(\frac{p_i-1}{p_i}\right)\times \frac{n!}{m!}=n!\times \prod _{i=1}^k\left(\frac{p_i-1}{p_i}\right)$res=φ(m!)×m!n!​=m!×i=1∏k​(pi​pi​−1​)×m!n!​=n!×i=1∏k​(pi​pi​−1​)

我们用 $ans$ans数组记录最后的式子的右边的东西， $ans\left[i\right]$ans[i]表示 $k$k到 $i$i时右边东西的值。 $jc\left[i\right]$jc[i]表示 $i!$i!。 $ny\left[i\right]$ny[i]表示 $i$i的逆元。

根据公式，很容易就能写出，答案 $=jc\left[n\right]\times ans\left[m\right]$=jc[n]×ans[m]。预处理出三个数组，就能做到 $O\left(1\right)$O(1)查询，这题就做完了，撒花~。

空间有点紧，不能都开 $longlong$long long，不该开的就不用开了。

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define oo (1e18)
#define ll long long
#define LL unsigned long long
#define hh puts("")
using namespace std;
int T,top,n,m,ny[10000005],ans[10000005],pr[6000005];
bool v[10000005];
ll r,jc[10000005];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
signed main(){
    scanf("%d%lld",&T,&r);
    jc[0]=jc[1]=1;
    ny[0]=ny[1]=1;
    ans[0]=ans[1]=1;
    for(int i=2;i<=10000000;i++){
        jc[i]=jc[i-1]*(ll)i%r;
        ny[i]=(ll)(r-r/i)*ny[r%i]%r;
        if(!v[i]) pr[++top]=i;
        for(int j=1;j<=top&&i*pr[j]<=10000000;j++){
            v[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
    for(int i=2;i<=10000000;i++){
        ans[i]=ans[i-1];
        if(!v[i]) ans[i]=(ll)ans[i]%r*(i-1)%r*ny[i]%r;
    }
    while(T--){
        n=read(),m=read();
        ll res=(ll)ans[m]%r*jc[n]%r;
        printf("%lld\n",res);
    }
    return 0;
}