1 条题解
-
1
考虑到 $\gcd(a,m!)=1\to \gcd(a+m!, m!)=1\to \gcd(a+k\cdot m!,m!)=1,k\in \mathbf Z_+$ 。
因此 中与 互质的个数,与 中的均相同。
而 中与 互质的数的个数为 $\displaystyle \boldsymbol \varphi(m!)=m!\prod_{p\in Prime}^m{p-1\over p}$ 。
故答案为 $\displaystyle {n!\over m!}\cdot \boldsymbol \varphi(m!)=n!\prod_{p\in Prime}^m{p-1\over p}$ 。
考虑线筛时分别用 维护 中的不含 因子的所有数乘积,与 因子的出现次数。
再分别用 维护 中不含 因子的所有数乘积,与 因子的出现次数。
询问 时,若 ,说明答案含有 因子,取模后为 ;否则 ,答案不含有 因子,则取模后为 。
参考代码(略丑)
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; typedef double db; #define fi first #define se second const int Lim=1e7, MAXN=Lim+10; int R; int prime[MAXN/10], cntprime, fc[MAXN], frac[MAXN], cntf[MAXN], infr[MAXN], cnti[MAXN]; inline int fpow(int a, int x) { int ans=1; for(;x;x>>=1,a=(ll)a*a%R) if(x&1) ans=(ll)ans*a%R; return ans; } inline void init() { frac[0]=frac[1]=infr[0]=infr[1]=1; for(int i=2,val; i<=Lim; ++i) { frac[i]=frac[i-1]; cntf[i]=cntf[i-1]; infr[i]=infr[i-1]; cnti[i]=cnti[i-1]; if(!fc[i]) { fc[i]=prime[++cntprime]=i; if(i==R) { infr[i]=(ll)infr[i]*(i-1)%R; --cnti[i]; } else { val=i-1; while(val%R==0) ++cnti[i], val/=R; infr[i]=(ll)infr[i]*val%R*fpow(i, R-2)%R; } } val=i; while(val%R==0) ++cntf[i], val/=R; frac[i]=(ll)frac[i]*val%R; for(int j=1; j<=cntprime; ++j) if(prime[j]*i>Lim||prime[j]>fc[i]) break; else fc[prime[j]*i]=prime[j]; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin>>T>>R; init(); int n, m; while(T--&&cin>>n>>m) { int res=(ll)frac[n]*infr[m]%R; int cnt=cntf[n]+cnti[m]; if(cnt>0) res=0; cout<<res<<"\n"; } cout.flush(); return 0; }
- 1
信息
- ID
- 2186
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 36
- 已通过
- 12
- 上传者