Educational Codeforces Round 88 E. Modular Stability

题目链接

Educational Codeforces Round 88 E. Modular Stability

思路

对于任意的非负整数$x$，我们要满足$x\%a\%b=x\%b\%a$。因为$a<b$，所以只有$b$为$a$的倍数时才满足条件。

因此，我们可以枚举最小的$a$，求出值域范围内有多少个它的倍数，然后使用组合数学计算答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 5e5 + 5, M = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, k;
int fac[N], infac[N];
int qmi(int a, int b, int c)
{int res = 1;while (b){if (b & 1)res = res * a % c;b >>= 1;a = a * a % c;}return res;
}
void init()
{fac[0] = infac[0] = 1;for (int i = 1; i <= n; i++){fac[i] = fac[i - 1] * i % mod;infac[i] = infac[i - 1] * qmi(i, mod - 2, mod) % mod;}
}
int C(int a, int b)
{return fac[a] * infac[b] % mod * infac[a - b] % mod;
}
int MOD(int x)
{return (x % mod + mod) % mod;
}
void solve()
{cin >> n >> k;init();if (n < k){cout << 0 << endl;}else{int ans = 0;for (int i = 1; i <= n - k + 1; i++) //假设最小的a[i]为i{int num = n / i - 1;if (num < k - 1) break;ans = (ans + C(num, k - 1)) % mod;}cout << MOD(ans) << endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}