CF1359E Modular Stability 题解
题目链接：CF1359E Modular Stability
题意：
求有多少个长度为 \(k\) 的序列 \(a\)，满足以下条件：
\(\forall 1 \le i < k,a_i < a_{i+1}\)
\(\forall 1 \le i \le k,1 \le a_i \le n\)
对于任意一个 \(1\) 至 \(k\) 的排列 \(p\)，满足 \[ \begin{aligned} &( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) \\[6pt]= &((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3} )\bmod \cdots \bmod a_{p_k}) \end{aligned} \] 其中 \(x\) 为任意非负整数。
结果对 \(998244353\) 取模。
输入格式：
输入一行两个整数 \(n,k\)，意义如题目描述所示。
输出格式：
输出一个整数表示答案。
数据范围：
\(1 \le n,k \le 5 \times 10^5\)。
考虑如何使得 \((x \bmod a) \bmod b = (x \bmod b) \bmod a\) ，其中 \(a < b\)
稍微搞一搞可以发现上面的式子等价于 \(x\equiv x + by \pmod{a}\) ，则 \(a \mid b\) 时恒成立
那么有 \(a_i \mid a_{i+1}\) ，其中 \(i < k\) 。因此我们只需要枚举 \(a_1\) ，然后看看有多少倍数合法，从里面选 \(k-1\) 个就好
时间复杂度 \(\mathcal{O}(n)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(1e6 + 15))
int fac[N],inv[N];
void init(int n)
{
fac[0] = 1, inv[0] = inv[1] = 1;
for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
for(int i = 2; i <= n; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = 2; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % mod;
}
int C(int n, int m)
{
if(!m) return 1;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
init((int)(1e6 + 5));
int n,k,res = 0; cin >> n >> k;
for(int i = 1; i <= n; i++)
{
if(n / i < k) break;
add(res, C(n / i - 1, k - 1));
}
cout << res << '\n';
return 0;
}参考文献：
