描述:
给定 \(n\) 个数,求其中取 \(k\) 个数,它们的 \(\gcd\) 为 \(t\) ,其中 \(t∈[1,m]\) 。
思路:
套路:
这里是求多个数的 \(\gcd\) 为 \(t\) ,那么可以设 \(f(i)\) 表示用 \(k\) 个数,组合是 \(i\) 的的方案数。
那么可以用容斥:
\(f(i)=sum-f(2i)-f(3i)-f(4i)\dots f(ki)\)
其中 \(sum\) 为组合是 \(i\) 的 倍数 的方案数, \(ki\) 为不大于 \(n\) 的最大整数。
代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long
#define PR pair<int,int>
using namespace std;
const int kN=1e6;
const int kMod=1e9+7;
int n,m,k;
int a[kN+5];
int num[kN+5];
LL fac[kN+5],inv[kN+5];
LL f[kN+5];
int v[kN];
LL Qpow(LL a,LL b){
LL res=1;
for(int i=0;(1<<i)<=b;++i){
if(b&(1<<i)){
res=(res*a)%kMod;
}
a=(a*a)%kMod;
}
return res;
}
void Init(){
fac[0]=1;
for(int i=1;i<=kN;++i){
fac[i]=(fac[i-1]*i)%kMod;
}
inv[kN]=Qpow(fac[kN],kMod-2);
for(int i=kN-1;i>=0;--i){
inv[i]=inv[i+1]*(i+1)%kMod;
}
}
LL C(LL n,LL m){
return fac[n]*inv[m]%kMod*inv[n-m]%kMod;
}
int main(){
Init();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
v[a[i]]++;
}
for(int i=1;i<=m;++i){
for(int j=i;j<=m;j+=i){
if(!v[j]){continue;}
num[i]+=v[j];
}
}
for(int i=m;i;--i){
if(!num[i]||num[i]<k){continue;}
f[i]=C(num[i],k);
for(int j=2*i;j<=m;j+=i){
f[i]-=f[j];
f[i]=(f[i]+kMod)%kMod;
}
}
for(int i=1;i<=m;++i){
printf("%lld ",f[i]);
}
return 0;
}
Undersea Palace