要求\(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\)的质数
预处理前缀积，二分即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// <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; } |
说点什么