1 条题解

  • 0
    @ 2021-11-19 9:47:53

    一个比较显然的结论,如果我们将一个数分解质因数。

    x=i=1npikix=\prod_{i=1}^n p_i^{k_i}

    那么 xx 的约数个数就是 i=1n(ki+1)\prod_{i=1}^n (k_i+1)

    考虑 (nk)=i=nk+1nik!\binom{n}{k}=\frac{\prod_{i=n-k+1}^n i}{k!}

    那么上面有 kk 个数,下面也有 nn 个数。

    先考虑把上下的 10610^6 以下的约数全部除掉。

    然后 10610^6 以上的约数都只会在上面,且每个数只会有一个这样的质因数,并且不会有重复。

    直接扫一遍就好了。


    代码
    #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
    上传者