题解 CF1359E 【Modular Stability】

fighter · 2020-06-05 08:34:19 · 题解

我们先拉出序列中最小的那个数a，假设现在有一个大于a的模数b，那么思考一下它们的顺序对答案的影响。

对于任意正整数x，我们要满足x\%a\%b= x\%b\%a，又因为b>a，所以x\%a\%b=x\%a，所以上式即x \equiv x\% b\pmod a

然后设x=tb+y，那么tb+y\equiv y \pmod a，由于t是任意的，所以只有当a|b时，等式恒成立。

那么意会一下，这个结论也可以推广到整个数列，于是我们得出结论：序列中的每一个数都是最小的那个数的倍数。

那么我们只要从1开始枚举最小的数，求出值域范围内有多少它的倍数，然后组合数选出k-1个即可（最小数自己是钦定的）。

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000005
#define P 998244353
using namespace std;

ll n, k;
ll fac[MAX], inv[MAX];

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%P;
    for(int i = 2; i <= n; i++) inv[i] = (P-P/i)*inv[P%i]%P;
    for(int i = 2; i <= n; i++) inv[i] = inv[i]*inv[i-1]%P;
}

ll C(ll n, ll m){
    if(!m) return 1;
    return fac[n]*inv[m]%P*inv[n-m]%P;
}

int main()
{
    init(MAX-1);
    cin >> n >> k;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(n/i < k) break;
        ans = (ans+C(n/i-1, k-1))%P;
    }
    cout << ans << endl;

    return 0;
}