Atcoder ABC227G 题解

Atcoder ABC277G 题解

link

给定 $n$、$k$，求 $C_n^k$ 的约数个数。

$1 \le n \le 10^{12}$，$1 \le k \le \min (n, 10^6)$

首先，一个数 $$n = \Pi_{i = 1}^{m} p_i^{k_i}$$ 的约数个数为 $$\Pi_{i = 1}^m \left(k_i+1\right)$$ 。

对组合数进行约分，$$C_n^k = \dfrac{n!}{(n-k)! \ k!} = \dfrac{\Pi_{i=n-k+1}^n i}{k!}$$。

我们分开考虑上下部分，用上半部分每个素数的个数减去下面的计算答案。

下部分因为 $k$ 的范围只有 $10^6$ ，所以我们可以预处理出 $10^6$ 以内的所有素数，对于每个素数 $p$，我们就可以求出 $p$、$2p$、$3p$ 等等中的质因子 $p$ 的数量和 $s$。

上部分比较难搞，因为范围达到 $10^{12}$，但我们惊奇地发现 $10^{12}$ 就是 $10^6$ 的平方，联想到一个性质：对于一个数 $n$，它最多有一个大于 $\sqrt{n}$ 的质因子。因此 $10^6$ 一下与下部分同样处理，最后判断一下如果不等于一，答案乘以 $2$。

TIP

这题 TM 输入要 long long，坑到我了。

CODE

#include <bits/stdc++.h>
using namespace std;

template <typename T> inline T read() {
	T x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define int long long

#define N 1000010
#define P 998244353

int n, k, a[N], b[N], vis[N], res = 1, t;

vector<int> pr;

void get_prime() {
	for (int i = 2; i < N; i ++) {
		if (!vis[i]) pr.push_back(i);
		for (int j = 0; j < pr.size() && i * pr[j] < N; j ++) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) break;
		}
	}
}

signed main() {
	get_prime();

	n = read<int>(), k = read<int>(), t = n - k;

	for (int i = 1; i <= k; i ++) {
		a[i] = i, b[i] = t + i;	
	}

	for (auto p : pr) {
		int cnt = 0;
		for (int i = p; i <= k; i += p) {
			while (a[i] % p == 0) a[i] /= p, cnt --;
		}
		for (int i = (t + p) / p * p; i <= n; i += p) {
			while (b[i - t] % p == 0) b[i - t] /= p, cnt ++;
		}
		res = res * (cnt + 1) % P;	
	}

	for (int i = t + 1; i <= n; i ++) {
		if (b[i - t] != 1) res = res * 2 % P;
	}

	printf("%lld\n", res);
	return 0;
}