Codeforces 1359 E. Modular Stability
题意:给出 nnn 和 kkk ,要求在 [1,n][1, n][1,n] 中找出不同的 kkk 个数,使得有规律,所有 aia_iai 必须能被最小值 a1a_1a1 整除。只要枚举 a1a_1a1 的值,然后计算组合数就行了。AC代码:const int N = 5e5 + 50;int n, k;const int mod = 998244353;int F[N], Finv[N],
·

题意:
给出 nnn 和 kkk ,要求在 [1,n][1, n][1,n] 中找出不同的 kkk 个数,使得
有规律,所有 aia_iai 必须能被最小值 a1a_1a1 整除。只要枚举 a1a_1a1 的值,然后计算组合数就行了。
证明一下:假设有一个数为 ata_tat 不能被 a1a_1a1 整除,那么设 x=atx=a_tx=at,则 x%a1...%at≠0x\%a_1...\%a_t≠0x%a1...%at=0 而 x%at=0x\%a_t=0x%at=0。
AC代码:
const int N = 5e5 + 50;
int n, k;
const int mod = 998244353;
int F[N], Finv[N], inv[N]; //F是阶乘,Finv是逆元的阶乘
void init()
{
inv[1] = 1;
for (int i = 2; i < N - 10; i++)
{
inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
} //递推求逆元
F[0] = Finv[0] = 1;
for (int i = 1; i < N - 10; i++)
{
F[i] = F[i - 1] * 1ll * i % mod;
Finv[i] = Finv[i - 1] * 1ll * inv[i] % mod;
}
}
int comb(int n, int m) //comb(n, m)就是C(n, m)
{
if (m < 0 || m > n)
return 0;
return F[n] * 1ll * Finv[n - m] % mod * Finv[m] % mod;
}
int main()
{
int T;
sdd(n, k);
init();
int ans = 0;
rep(i, 1, n)
{
ans += comb(n / i - 1, k - 1) % mod;
ans %= mod;
}
pd(ans);
return 0;
}
更多推荐

所有评论(0)