先放知識點：
莫比烏斯反演
盧卡斯定理求組合數
乘法逆元
快速冪取模

GCD of Sequence

Alice is playing a game with Bob. Alice shows N integers a 1, a 2, …, a N, and M, K. She says each integers 1 ≤ a i ≤ M. And now Alice wants to ask for each d = 1 to M, how many different sequences b 1, b 2, …, b N. which satisfies : 1. For each i = 1…N, 1 ≤ b[i] ≤ M 2. gcd(b 1, b 2, …, b N) = d 3. There will be exactly K position i that ai != bi (1 ≤ i ≤ n)Alice thinks that the answer will be too large. In order not to annoy Bob, she only wants to know the answer modulo 1000000007.Bob can not solve the problem. Now he asks you for HELP! Notes: gcd(x 1, x 2, …, x n) is the greatest common divisor of x 1, x 2, …, x n

Input

The input contains several test cases, terminated by EOF. The first line of each test contains three integers N, M, K. (1 ≤ N, M ≤ 300000, 1 ≤ K ≤ N) The second line contains N integers: a 1, a 2, …, a n (1 ≤ a i ≤ M) which is original sequence.

Output

For each test contains 1 lines : The line contains M integer, the i-th integer is the answer shows above when d is the i-th number.

Sample Input

3 3 3 3 3 3 3 5 3 1 2 3 1 2 3 4

Sample Output

7 1 0 59 3 0 1 1 1 2

Hint

In the first test case : when d = 1, {b} can be : (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 2) (2, 1, 1) (2, 1, 2) (2, 2, 1) when d = 2, {b} can be : (2, 2, 2) And because {b} must have exactly K number(s) different from {a}, so {b} can't be (3, 3, 3), so Answer = 0

盧卡斯求組合數是log級別的所以沒問題

#include <bits/stdc++.h> using namespace std; const int maxn = 310000; const int mod = 1000000007; int n, m, k; int prime[maxn], tot, mu[maxn]; //莫比烏斯函數 bool vis[maxn]; long long fac[maxn], rev[maxn]; //乘法逆元，和盧卡斯定理 long long F[maxn], f[maxn]; //莫比烏斯反演 int a[maxn]; int cnt[maxn]; //對于d,有多少a[i]是d的倍數 long long extend_gcd(long long a, long long b, long long &x, long long &y) {//擴展歐幾里得if (a == 0 && b == 0)return -1;if (b == 0){x = 1;y = 0;return a;}long long d = extend_gcd(b, a % b, y, x);y -= a / b * x;return d; } long long mod_rev(long long a, long long n) //乘法逆元lucas用 {long long x, y;long long d = extend_gcd(a, n, x, y);if (d == 1)return (x % n + n) % n;elsereturn -1; }void init() //線性篩求莫比烏斯函數 {tot = 0;mu[1] = 1;for (int i = 2; i < maxn; i++){if (!vis[i]){prime[tot++] = i;mu[i] = -1;}for (int j = 0; j < tot; j++){if (i * prime[j] >= maxn)break;vis[i * prime[j]] = 1;if (i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else{mu[i * prime[j]] = -mu[i];}}}fac[0] = rev[0] = 1;for (int i = 1; i < maxn; i++){fac[i] = fac[i - 1] * i % mod;//預處理盧卡斯定理參數rev[i] = mod_rev(fac[i], mod);//預處理逆元} }long long quick_mod(long long a, long long b) {long long ans = 1;a %= mod;while (b){if (b & 1){ans = ans * a % mod;b--;}b >>= 1;a = a * a % mod;}return ans; }long long Lucas(long long m, long long n) {if (n == 0)return 1;long long ans = fac[m] * rev[n] % mod * rev[m - n] % mod;return ans; }int main() {init();while (scanf("%d%d%d", &n, &m, &k) != EOF){memset(cnt, 0, sizeof cnt);memset(f, 0, sizeof f);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);cnt[a[i]]++;}for (int i = 1; i <= m; i++)for (int j = i + i; j <= m; j += i)cnt[i] += cnt[j];for (int i = 1; i <= m; i++){long long p = cnt[i];if (k - n + p < 0){F[i] = 0;continue;}F[i] = Lucas(p, k - n + p) * quick_mod(m / i - 1, k - n + p) % mod * quick_mod(m / i, n - p) % mod;}for (int i = 1; i <= m; i++){if (F[i] == 0)f[i] = 0;elsefor (int j = i; j <= m; j += i){f[i] += mu[j / i] * F[j];f[i] %= mod;}printf("%lld", (f[i] + mod) % mod);if (i != m)printf(" ");}printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的数学--数论--HDU 4675 GCD of Sequence(莫比乌斯反演+卢卡斯定理求组合数+乘法逆元+快速幂取模）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。