【BZOJ2186】【SDOI2008】沙拉公主的困惑

要求\(n!\)范围内与\(m!\)互质的数的个数

根据欧几里得boy的定理，\((x,m!)=1\)意味着\((x\bmod m!,m!)=1\)

也就是说只要求出\(\varphi(m!)\)再乘上\(\frac{n!}{m!}\)

阶乘及其逆元都是可以\(O(n)\)求出的

根据定义，\(\varphi(m!)=m!\prod(p-1)p^{-1}\)，其中\(p\)为不大于\(m\)的质数

预处理前缀积，二分即可。

// <2186.cpp> - Tue Aug  2 20:19:22 2016
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
     return fh*res;
}
const int MAXN=10000001;
const int INF=1e9;
int mod;
int jc[MAXN],nj[MAXN],qz[MAXN];
int tot,pr[MAXN];
bool np[MAXN];
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
int main(){
    int T=gi();mod=gi();int lim=min(mod,MAXN);
    jc[0]=1;for(int i=1;i<lim;i++)jc[i]=1ll*jc[i-1]*i%mod;
    nj[lim-1]=qpow(jc[lim-1],mod-2);
    for(int i=lim-1;i;i--)nj[i-1]=1ll*nj[i]*i%mod;
    for(int i=2;i<lim;i++){
        if(!np[i])pr[++tot]=i;
        for(int j=1;j<=tot&&pr[j]*i<lim;j++){
            np[pr[j]*i]=1;
            if(!(i%pr[j]))break;
        }
    }
    qz[0]=1;for(int i=1;i<=tot;i++)qz[i]=1ll*qz[i-1]*(pr[i]-1)%mod*nj[pr[i]]%mod*jc[pr[i]-1]%mod;
    while(T--){
        int n=gi(),m=gi();
        int l=upper_bound(pr+1,pr+tot+1,m)-pr-1;
        printf("%d\n",1ll*qz[l]*jc[n]%mod);
    }
    return 0;
}

// <2186.cpp> - Tue Aug 2 20:19:22 2016

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=10000001;

const int INF=1e9;

int mod;

int jc[MAXN],nj[MAXN],qz[MAXN];

int tot,pr[MAXN];

bool np[MAXN];

int qpow(int x,int y){

int res=1;

while(y){

if(y&1)res=1ll*res*x%mod;

x=1ll*x*x%mod;

y>>=1;

}

return res;

}

int main(){

int T=gi();mod=gi();int lim=min(mod,MAXN);

jc[0]=1;for(int i=1;i<lim;i++)jc[i]=1ll*jc[i-1]*i%mod;

nj[lim-1]=qpow(jc[lim-1],mod-2);

for(int i=lim-1;i;i--)nj[i-1]=1ll*nj[i]*i%mod;

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

if(!np[i])pr[++tot]=i;

for(int j=1;j<=tot&&pr[j]*i<lim;j++){

np[pr[j]*i]=1;

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

}

qz[0]=1;for(int i=1;i<=tot;i++)qz[i]=1ll*qz[i-1]*(pr[i]-1)%mod*nj[pr[i]]%mod*jc[pr[i]-1]%mod;

while(T--){

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

int l=upper_bound(pr+1,pr+tot+1,m)-pr-1;

printf("%d\n",1ll*qz[l]*jc[n]%mod);

}

return 0;

}