GCD of Sequence HDU

题面

点我看题

题解

这题没必要反演, 可以用

看完题应该能得到个基本(不是答案)的公式

cnt[i] 代表 1~n a数组中有多少个数含有因子 i,

则对于 ans[i], 有个不算太正确的公式

分为两部分, 对于 1~n a数组 不含有因子 i 的一部分, 和 含有因子 i 的一部分

(1~m 中含有因子 i 的数有 m/i 个)

当然 k < n - cnt[i], ans[i] = 0

cur = (( left lfloor frac{m}{i} ight floor^{k - cnt[i]} ) + ( C_{cnt[i]}^{k - (n - cnt[i])} * left lfloor frac {m - i}{i} ight floor ^{k - (n - cnt[i])} ))

为什么说这个式子不是答案呢, 明明就是答案~

其实当 每个数都是选的含有因子 i 的数, 但是忘了 2i, 12i, 2i, 6i, 他们的公因数不是 i 而是 2*i

加上 i 的倍数, 减去 2i 的倍数, 减去 3i 的倍数, 加上 6*i 的倍数...

这不就是 最简单的容斥吗?

直接倒着写, 就可以维护 ans[p * i] (p > 1) 的信息了, 容斥直接计算就行了

这是个调和级数 nlog 不是 n*n

当然想用反演的话

设 f(i) = (sum_{c[1]} sum_{c[2]} .... sum_{c[n]} [gcd(c[1], c[2], ..., c[n]) == i])

然后也是倒着计算, 这样算 f(i) = (sum_{i | d} mu(d/i) * F(d)) 的时候 F(d) 已经算过了, 也是调和级数的复杂度

ll n, m, _, k;
ll cnt[N], fac[N], facinv[N], inv[N], ans[N], f[N];
int miu[N], prime[N], tot;
bool v[N];

void getmiu(int n) {
    miu[1] = fac[0] = facinv[1] = facinv[0] = fac[1] = inv[1] = 1;
    rep (i, 2, n) {
        if (!v[i]) prime[++tot] = i, miu[i] = -1;
        for (int j = 1; prime[j] <= n / i && j <= tot; ++j) {
            v[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
            else miu[i * prime[j]] = -miu[i];
        }
	fac[i] = fac[i - 1] * i % mod;
	inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	facinv[i] = facinv[i - 1] * inv[i] % mod;
    }
}

ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ans = a * ans % mod;
    return ans;
}

ll C(int x, int y, int p) {
    if (y == 0 || x == p) return 1;
    if (x < 0 || y < 0 || y > x) return 0;
    return (ll) fac[x] * facinv[y] % p * facinv[x - y] % p;
}

int main() {
    IOS; getmiu(3e5);
    while (cin >> n >> m >> k) {
	rep (i, 1, m) cnt[i] = 0;
	rep (i, 1, n) cin >> _, ++cnt[_];
	rep (i, 1, m) for (int j = i << 1; j <= m; j += i) cnt[i] += cnt[j];

	per (i, m, 1) {
	    int d = n - cnt[i]; f[i] = ans[i] = 0;
	    if (k < d) continue;
	    f[i] = qpow(m / i, d) * qpow(m / i - 1, k - d) % mod * C(cnt[i], k - d, mod) % mod;
            for (int d = i; d <= m; d += i) ans[i] = ((ans[i] + f[d] * miu[d / i]) % mod + mod) % mod;
	}

	cout << ans[1]; rep (i, 2, m) cout << ' ' << ans[i]; cout << '
';
    }
    return 0;
}