Educational Codeforces Round 88 (Rated for Div. 2) E. Modular Stability（数论） 题意 题解 代码
题目链接：https://codeforces.com/contest/1359/problem/E
有一大小为 $k$ 的数组，每个元素的值在 $[1,n]$ 间，若元素间两两不等，问有多少数组对于任意非负整数 $x$ 满足：
$x \% a_{1} \% a_{2} \% ... \% a_{k} = x \% a_{p1} \% a_{p2} \% ... \% a_{p_k}$
其中，$p$ 为 $k$ 的任一种排列，$a_1<a_2<...<a_k$ 。
题解
易得该式的结果取决于最小的 $a_i$ 。
假设数组 $a$ 中最小的数为 $a_1$，设 $x = na_1 + m ( n ≥ 0, 0 ≤ m < a_1 )$，该式的值即为 $m$，由此推出 $x \% a_i$ 后 $\% a_1$ 仍为 $m$，即 $(n_1a_1 + m) \% a_i = n_2a_1 + m$，所以 $a_i$ 为 $a_1$ 的倍数。
又因为 $k$ 个数两两不同，所以枚举 $a_1$ 的值，从余下 $frac{n}{a_1} - 1$ 个 $a_1$ 的倍数中选取 $k - 1$ 个即可。
即 $sum_{i = 1}^{n} C_{frac{n}{i} - 1}^{k - 1}$ 。
代码
#include <bits/stdc++.h> using ll = long long; using namespace std; const int mod = 998244353; ll fpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } ll inv(ll x) { return fpow(x, mod - 2); } ll C(ll n, ll m) { if (n < m) return 0; ll res = 1; ll mi = min(m, n - m); for (int i = 1; i <= mi; i++) res = res * (n - i + 1) % mod * inv(i) % mod; return res; } int main() { int n, k; cin >> n >> k; ll ans = 0; for (int i = 1; i <= n; i++) ans += C(n / i - 1, k - 1), ans %= mod; cout << ans << " "; }