【Luogu】P2155沙拉公主的困惑（数论）

　　题目链接

　　数论果然是硬伤qwq　　还是智商上的硬伤

　　我们来讲两个道理

　　No.1　　求1~i！中与i！互质的数的个数

　　实际上就是求i!的欧拉函数

　　有如下递推式：

　　f[1]=1

　　if(i为合数)　　f[i]=f[i-1]*i;

　　if(i为素数)　　f[i]=f[i-1]*(i-1);

　　证明如下

　　首先我们有个神奇引理。叫做：如果n=p1^a1*p2^a2*………………*pk^ak是n的素数幂乘积表达式，那么有

　　$phi[n]=n*\frac{p1-1}{p1}*\frac{p2-1}{p2}*……*\frac{pk-1}{pk}$

　　所以说我们的$phi[n!]=n!*\frac{p1-1}{p1}*\frac{p2-1}{p2}*……*\frac{pk-1}{pk}$

　　那么首先我们知道n!是从1乘到n（废话）

　　那么注意（敲黑板）phi[n]的质因子就是1到n里的质数对不对

　　我们现在就把所有的分母约掉

　　所以phi[n]就变成了(所有合数的乘积)*(所有质数-1的乘积)

　　于是递推式得证

　　然后第二个问题，就是如果gcd(a,b)==1，那么gcd(a*k+b,b)=1

　　这个东西有什么用呢？

　　我们设n!为mul[n]。

　　由于n>=m，所以mul[n]>=mul[m]，并且mul[n]一定是mul[m]的整数倍。

　　这样我们发现$mul[n]=mul[m]*\frac{mul[n]}{mul[m]}$

　　所以说1到mul[n]中和mul[m]互质的，就等于1~mul[m]中与mul[m]互质的，再乘上$\frac{mul[n]}{mul[m]}$

　　然后逆元乱搞搞就好了qwq

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cstdlib>

#define maxn 10000020

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

bool s[maxn];

int prime[maxn],tot;

int mul[maxn];

int f[maxn];

long long Pow(long long n,int x,int p){

    long long ans=;

    while(x){

        if(x&)    ans=(ans*n)%(long long)p;

        n=(n*n)%(long long)p;

        x>>=;

    }

    return ans;

}

int main(){

    int T=read(),p=read();

    s[]=mul[]=f[]=;

    for(int i=;i<=maxn;++i){

        if(!s[i])

            prime[++tot]=i;

        for(int j=;j<=tot&&(long long)prime[j]*i<=maxn;++j){

            s[i*prime[j]]=;

            if(!(i%prime[j]))    break;

        }

    }

    for(int i=;i<=maxn;++i){

        mul[i]=((long long)mul[i-]*(long long)i)%(long long)p;

        if(s[i])    f[i]=((long long)f[i-]*(long long)i)%(long long)p;

        else         f[i]=((long long)f[i-]*(long long)(i-))%(long long)p;

    }

    while(T--){

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

        printf("%lld\n",(long long)(((long long)f[m]*(long long)mul[n])%(long long)p*Pow(mul[m],p-,p))%p);

    }

    return ;

}

巴特西

【Luogu】P2155沙拉公主的困惑（数论）

最新文章

热门文章