codeforces-Ed88-E

codeforces-Ed88-E

七月 08, 2020

E. Modular Stability

  • 题意

给出一个n
要求统计出有多少长度为k的数组 1<=i<=k; 1<=ai<=n
使得它的所有排列 对于任何数x都有
x mod a1 mod a2 mod a3 mod a4 … mod ak = x mod a[i1] mod a[i2] mod a[i3] … mod a[ik]

i1 , i2 , i3 …. ik 是 1到k的所有排列情况

  • 题解

首先需要发现一个事实即
当且仅当 所有ai mod min{aj | 1<=j<=k } ==0 或者说所有ai都能被其中最小的数aj整除
那么无论数组ai如何排列 对任意数x取模的最终结果是相同的

假设 a为数组中最小的数
x mod a mod ka =x mod ka mod a = x mod a

假设数组中存在一个m mod a !=0
那么 若x=a
则 x mod a=0 之后无论mod何数都为0
而 x mod m!=0 最后不一定为0

剩下的就是用逆元取组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

# define Turnoff std::ios::sync_with_stdio(false)

const ll Max=5e5+5;
const ll mod=998244353;
ll fac[Max];
void intn(){
    fac[0]=1;
    for(ll i=1;i<Max;i++)fac[i]=(fac[i-1]*i)%mod;
    //cout<<endl;
}
ll qpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1)ans=(ans*x)%mod;
        x=(x*x)%mod;y>>=1;
    }
    return ans;
}
ll combin(ll total,ll need){
    //cout<<(fac[need]*fac[total-need])%mod<<endl;
    //cout<<qpow(fac[need]*fac[total-need]%mod,mod-2)<<endl;
    return (fac[total]*qpow(fac[need]*fac[total-need]%mod,mod-2))%mod;
}
int main(){
    Turnoff;
    intn();ll ans=0;
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        if(n/i<k)continue;
        ll have=n/i-1;
        //cout<<have<<" "<<k-1<<endl;
        //cout<<combin(have,k-1)<<endl;
        ans=(ans+combin(have,k-1))%mod;
    }
    cout<<ans<<endl;
}