2015
09-17

# GCD of Sequence

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 209    Accepted Submission(s): 65

Problem Description
Alice is playing a game with Bob.
Alice shows N integers a1, a2, …, aN, and M, K. She says each integers 1 ≤ ai ≤ M.
And now Alice wants to ask for each d = 1 to M, how many different sequences b1, b2, …, bN. which satisfies :
1. For each i = 1…N, 1 ≤ b[i] ≤ M
2. gcd(b1, b2, …, bN) = 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(x1, x2, …, xn) is the greatest common divisor of x1, x2, …, xn

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: a1, a2, …, an (1 ≤ ai ≤ 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

Sample Output
7 1 0
59 3 0 1 1
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


Source

Recommend
zhuyuanchen520

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

//

const int V = 300000 + 50;
const int inf = 0x7fffffff;
const int mod = 1000000000 + 7;
int n, m, k;
int sum[V];
__int64 ans[V], d[V], e[V];
__int64 Quick_Pow(__int64 a, __int64 b) {
__int64 res = 1;
while(b) {
if(b & 1)
res = (res * a) % mod;
b /= 2;
a = (a * a) % mod;
}
return res % mod;
}
__int64 Cal(__int64 n, __int64 k) {
return (d[n] * e[k] % mod) * e[n - k] % mod;
}
int main() {
int i, j;
d[0] = e[0] = 1;
for(i = 1; i < V; ++i) {
d[i] = (d[i - 1] * i) % mod;
e[i] = Quick_Pow(d[i], mod - 2);
}
while(~scanf("%d%d%d", &n, &m, &k)) {
memset(sum, 0, sizeof(sum));
for(i = 0; i < n; ++i) {
int temp;
scanf("%d", &temp);
sum[temp]++;
}
for(i = m; i >= 1; --i) {
int sum_d = 0;
for(j = i; j <= m; j += i)
sum_d += sum[j];
if(n - sum_d > k) {
ans[i] = 0;
continue;
}
ans[i] = (Quick_Pow(m / i, n - sum_d) * Quick_Pow(m / i - 1, k - (n - sum_d)) % mod) * Cal(sum_d, k - (n - sum_d)) % mod;
//减去重复的
for(j = 2 * i; j <= m; j += i)
ans[i] = (ans[i] - ans[j] + mod) % mod;
}
for(i = 1; i < m; ++i)
printf("%I64d ", ans[i]);
printf("%I64d\n", ans[m]);
}
}