1 条题解
-
0
一个比较显然的结论,如果我们将一个数分解质因数。
那么 的约数个数就是 。
考虑 。
那么上面有 个数,下面也有 个数。
先考虑把上下的 以下的约数全部除掉。
然后 以上的约数都只会在上面,且每个数只会有一个这样的质因数,并且不会有重复。
直接扫一遍就好了。
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5,mod=998244353; int k,p[N],cnt,b[N],p1[N],ans=1; ll p2[N],n; void work(int maxn){ for(int i=2;i<=maxn;i++){ if(!b[i])p[++cnt]=i; for(int j=1;j<=cnt&&i*p[j]<=maxn;j++){ b[i*p[j]]=1; if(i%p[j]==0)break; } } } int main(){ scanf("%lld%d",&n,&k); work(1e6); for(int i=1;i<=k;i++)p1[i]=i; for(ll i=n-k+1;i<=n;i++)p2[i-(n-k)]=i; ll T=p2[1]; for(int i=1;i<=cnt;i++){ int sum=0; for(int j=p[i];j<=k;j+=p[i])for(;p1[j]%p[i]==0;p1[j]/=p[i])sum--; for(int j=p[i]-(T-1)%p[i];j<=k;j+=p[i])for(;p2[j]%p[i]==0;p2[j]/=p[i])sum++; ans=1ll*ans*(sum+1)%mod; } for(int i=1;i<=k;i++)if(p2[i]!=1)ans=2ll*ans%mod; printf("%d",ans); }
- 1
信息
- ID
- 44
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者