简要题意：
求在 (n) 个数中选 (k) 个数使其 (gcd) 分别为 (1) ~ (m) 的个数。(m = max_{i=1}^n a_i).
这是某洛谷月赛的 ( ext{T2})，有一定思维难度。
子任务 (1)
子任务 (1) ：(n leq 10)，(m leq 10^6)，(k leq 10)
暴力枚举 (k) 个数记录 ( ext{gcd}) 即可。
时间复杂度：(O(C_n^k log C_n^k)).
实际得分：(10pts).
子任务 (2)
子任务 (2)：(n,m,k leq 10^3).
给一些简单 ( ext{dp}) 乱搞的部分分。
子任务 (3)
子任务 (3)：(n leq 10^6)，(m leq 10^3)，(k leq 2).
预处理两两 (gcd). 但不是 (O(n^2 log m)) 的那种，而是预处理所有 (leq 10^3) 的数的个数记为 (f)，在 (f) 上两两匹配 (gcd) 记录个数即可。
时间复杂度：(O(m^2 log m)).
实际得分：(5pts).
子任务 (4)
子任务 (4)：(n,m leq 10^6)，(k leq 1)
这是个送分的子任务，统计每个数出现的次数即可。
时间复杂度：(O(n)).
实际得分：(5pts).
子任务 (5)
子任务 (5)：(n,m leq 10^6)，(k leq 2).
似乎不能暴力统计两两 (gcd) 了。所以这个子任务想要解决必须写正解，如果你会乱搞可以试一试。
子任务 (1) ~ (6)
对于 (100 \%) 的数据，(n,m leq 10^6),(1 leq k leq n).
我们需要考虑高级的 ( ext{dp}) 方式。
用 (g_i) 表示选出 (k) 个数，其 ( ext{gcd}) 为 (i) 的倍数 的个数。这里我们要考虑容斥，不是很简单的样子。
因为在所有是 (i) 的倍数中选 (k) 个用组合，但是不完全正确，因为 (g_i) 很有能计算重复，所以我们用 容斥 计算，把所有的 (g_j (i | j space space ext{and} space space i ot = j)) 全部减掉，然后对它们的和进行组合。
如何计算组合呢？我们可以预处理 阶乘逆元 然后 (O(1)) 回答。
时间复杂度：(O(n + m) + sum_{i=1}^m O ig(lfloor frac{m}{i} floor ig) = O(n + m log m)).
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int N=1e6+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
ll f[N],inv[N],invf[N];
ll g[N]; int t[N],n,m,k;
inline ll calc(int x,int y) {
return x<y?0:(f[x]*invf[y]%MOD*invf[x-y]%MOD);
} //组合
int main(){
n=read(),m=read(),k=read();
f[0]=invf[0]=1;
for(int i=1;i<=n;i++) {
inv[i]=(i==1)?1:(inv[MOD%i]*(MOD-MOD/i)%MOD);
f[i]=f[i-1]*i%MOD; invf[i]=invf[i-1]*inv[i]%MOD; //处理逆元，阶乘逆元
t[read()]++; //记录桶
} for(int i=m;i;i--) {
int cnt=0; //记录和
for(int j=1;i*j<=m;j++) cnt+=t[i*j],g[i]=(g[i]-g[i*j]+MOD)%MOD; //容斥减掉 , 统计和
g[i]=((g[i]+calc(cnt,k))%MOD+MOD)%MOD; //和的组合
} for(int i=1;i<=m;i++) printf("%lld ",g[i]);
return 0;
}