题解：P6298 齿轮

· · 题解

题意

给定 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;
}

:::