AT_abc227_g [ABC227G] Divisors of Binomial Coefficient

思路

首先需要知道一个事情，对于一个数 $x = \prod{p_i^{c_i}}$，它的约数个数是：

$$\prod{(c_i + 1)}$$

那么先将 $\binom{k}{n}$ 展开：

$$\frac{\prod_{i = n - k + 1}^{n}i}{k!}$$

发现一个数的约数个数只与其唯一分解后的指数有关，考虑统计每一个质数所对应的指数。

因为一个数 $x$，大于 $\sqrt{n}$ 的质因子只会有一个。证明很简单，考虑反证法，如果有两个大于 $\sqrt{n}$ 的质因子，二者相乘一定大于 $n$。

那么，我们直接筛出 $1 \sim \sqrt{n}$ 的质数。对于 $k!$ 的处理我们可以直接在筛质数的过程中处理掉，时间复杂度 $\Theta(\sqrt{n} \ln n \log n)$。

接着处理分子。考虑枚举质数，暴力将 $[n - k + 1,n]$ 的数去除掉当前枚举的质数，时间复杂度是 $\Theta(k \ln k \log n)$ 的。

然后去除掉小于 $\sqrt{n}$ 的约数，就最多剩下一个约数了。暴力加入即可。

因为值域较大，需要开 umap 存储。

Code

#include <bits/stdc++.h>
#define re register
#define int long long
#define Mul(a,b) (((a) % mod) * ((b) % mod) % mod)

using namespace std;

const int N = 1e6 + 10,mod = 998244353;
int n,k,ans = 1;
int cnt[N];
bool vis[N];
vector<int> v,p;
unordered_map<int,int> num;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void init(){
    vis[1] = true;
    for (re int i = 2;i <= 1e6;i++){
        if (!vis[i]){
            p.push_back(i);
            if (i <= k) cnt[i]--;
            for (re int j = 2;i * j <= 1e6;j++){
                vis[i * j] = true;
                int x = i * j,tot = 0;
                if (x <= k){
                    while (x % i == 0) x /= i,tot++;
                    cnt[i] -= tot;
                }
            }
        }
    }
}

signed main(){
    n = read(),k = read();
    init();
    for (re int i = 1;i <= k;i++) v.push_back(n - i + 1);
    if (v.empty()) goto End;// 特判，不然会 RE
    for (auto x:p){
        int t = n - (n / x) * x;
        for (re int i = t;i < v.size();i += x){
            int tot = 0;
            while (v[i] % x == 0) v[i] /= x,tot++;
            cnt[x] += tot;
        }
    }
    for (auto x:v){
        if (x != 1) num[x]++;
    }
    for (auto x:v){
        ans = Mul(ans,num[x] + 1); num[x] = 0;
    }
    End:;
    for (re int i = 1;i <= 1e6;i++) ans = Mul(ans,cnt[i] + 1);
    printf("%lld",ans);
    return 0;
}