自动搬运

查看原文

来自洛谷，原作者为

	Chronostatis 老师，我的作业会发光！

搬运于2025-08-24 22:19:28，当前版本为作者最后更新于2025-08-14 18:54:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定 $n$ 个数以及两个整数 $m, k$，现要选取 $k$ 个整数出来，要求对每个 $1 \le i \le m$ 求出，选出来的整数的最大公因数为 $i$ 的方案数。

思路

我们先来观察最大公因数的性质，若 $x$ 为集合 $S$ 的 $\gcd$，那么 $x$ 的所有因数都是 $S$ 的公因数。

我们可以对一个数计算出其倍数的个数 $cnt_i$，那么从中选 $k$ 个的方案数就是 $\text C _ {cnt_i} ^ k$。但是，由上面的讨论可知，这里面包含了其倍数的答案，所以我们对每个数的答案都减去其大于本身的倍数的答案总和。因为一个数的倍数总是大于等于这个数，所以我们需要倒着处理答案。

时间复杂度：$O(m \log m)$。

空间复杂度：$O(n)$。

:::info[对题解审核员的声明] 这篇题解的代码在时间、空间复杂度上均没有问题，且讨论区仍有题解没有声明时间、空间复杂度，因此我不能理解您对这篇题解的评价，并且请您评价时留下名字，方便私信交流。 :::

:::info[代码]

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 1e6 + 10, MOD = 1e9 + 7;

int n, m, k, a[MAXN], cnt[MAXN];
ll ans[MAXN], fac[MAXN], inv[MAXN];

ll qpow(ll x, ll y) {
  ll res = 1;
  for (; y; y >>= 1, (x *= x) %= MOD) {
    if (y & 1) (res *= x) %= MOD;
  }
  return res;
}

void Init(int _n) {
  fac[0] = inv[0] = 1;
  for (int i = 1; i <= _n; i++) {
    fac[i] = fac[i - 1] * i % MOD;
  }
  inv[_n] = qpow(fac[_n], MOD - 2);
  for (int i = _n; i > 1; i--) {
    inv[i - 1] = inv[i] * i % MOD;
  }
}

ll C(int n, int m) {
  return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  Init(n);
  for (int i = m; i >= 1; i--) {
    int c = 0;
    for (int j = i; j <= m; j += i) {
      c += cnt[j];
    }
    ans[i] = C(c, k);
    for (int j = i << 1; j <= m; j += i) {
      ans[i] = (ans[i] - ans[j] + MOD) % MOD;
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << ans[i] << ' ';
  }
  return 0;
}

:::