2784: 数列的GCD
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
给出一个长度为N的数列{a[n]}，1<=a[i]<=M(1<=i<=N)。 现在问题是，对于1到M的每个整数d，有多少个不同的数列b[1], b[2], ..., b[N]，满足： (1)1<=b[i]<=M(1<=i<=N)； (2)gcd(b[1], b[2], ..., b[N])=d； (3)恰好有K个位置i使得a[i]<>b[i](1<=i<=N) 注：gcd(x1,x2,...,xn)为x1, x2, ..., xn的最大公约数。 输出答案对1,000,000,007取模的值。
输入
第一行包含3个整数，N，M，K。 第二行包含N个整数：a[1], a[2], ..., a[N]。
输出
输出M个整数到一行，第i个整数为当d=i时满足条件的不同数列{b[n]}的数目mod 1,000,000,007的值。
样例输入 复制
3 3 3
3 3 3
样例输出 复制
7 1 0
提示
in
3 5 3
1 2 3
out
59 3 0 1 1
【样例1解释】
当d=1，{b[n]}可以为：(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1)。
当d=2，{b[n]}可以为：(2, 2, 2)。
当d=3，因为{b[n]}必须要有k个数与{a[n]}不同，所以{b[n]}不能为(3, 3, 3)，满足条件的一个都没有。
【数据说明】
对于30%的数据，1<=N<=20, 1<=M<=2。
对于50%的数据，1<=N,M<=1000。
对于70%的数据，1<=N,M<=10000。
对于100%的数据，1<=N,M<=300000, 1<=K<=N, 1<=a[i]<=M。