I题 小朋友你是否有很多问号
这个题我的基本思路就是对于每个数进行质因数分解，假如这个数分解成了p1*p2*...*px（这里忽略次方，因为没有意义）,那么n个数中与这个数不互质的数则可以通过容斥原理计算出来，即为sum=num[p1]+num[p2]+...num[p1*p2*...*px]，num[i]即为这n个数中能被i整除的数的个数，这个遵循奇加偶减即可，然后就知道了这n个数中与其互质的数为n-sum个，这样这个数对于答案的贡献就是a[i]*C(n-sum,m)，（C(n,m)为高中组合数学），然后对于每个数字都当作m元公倍数计算一遍即可。
因为ai最大为100000，而2*3*5*7*9*11*13*15>100000，所以每个数最多分解成6个不同的质数，因此每个数分解出来之后最多有2^6（=64）个组合，（即p1*p2*p3可以组合成p1,p2,p1*p2,p1*p3,p2*p3,p1*p2*p3），这样每个组合都可以使得对应的num[]加1，列如p1*p3可以使得num[p1*p3]加1，这样我们就可以用64*n的复杂度计算出num数组，而且可以保证即使最大的p1*p2*...*px也不会超过100000（这个显而易见）,然后再用64*n的复杂度计算出每个数对应的sum，进而得到答案。建议进行组合时用状压，这样比较方便好写。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int MAX_N=101000;
const long long MOD=998244353;
vector<int>v[MAX_N];
int prime[1010],tot=0;
bool vis[1010];
void init(int x){//求质数
int i,j;
for(i=2;i<=x;i++){
if(vis[i])
continue;
prime[++tot]=i;
for(j=i+i;j<=x;j+=i)
vis[j]=true;
}
}
int p[MAX_N][7],cnt;
int tt[MAX_N];
int num[MAX_N];
long long F[MAX_N];
long long b[MAX_N];
long long pow_mod(long long a,long long n,long long m){
long long ans=1;
while(n){
if(n&1){
ans=(ans*a)%m;
}
a=(a*a)%m;
n>>=1;
}
return ans;
}
long long C(int n,int m){//求组合数，提前预处理出阶乘数组F
return F[n]*pow_mod(F[m]*F[n-m]%MOD,MOD-2,MOD)%MOD;
}
int main(void){
int n,m,i,j,k,x;
init(1000);
scanf("%d%d",&n,&m);
F[0]=1;
for(i=1;i<=n;i++)
F[i]=i*F[i-1]%MOD;
for(i=1;i<=n;i++){
scanf("%d",&x);
b[i]=x;
cnt=0;
for(j=1;j<=tot;j++){
if(x==1)
break;
if(x%prime[j]==0){
while(x%prime[j]==0)
x/=prime[j];
p[i][cnt++]=prime[j];
}
}
if(x!=1)
p[i][cnt++]=x;
for(j=0;j<(1<<cnt);j++){//用每个数分解的质数进行组合计算出num数组
int s=1;
for(k=0;k<cnt;k++){
if(j&(1<<k)){
s*=p[i][k];
}
}
num[s]++;
}
tt[i]=cnt;
}
long long ans=0;
for(i=1;i<=n;i++){
cnt=tt[i];
int res=0;
for(j=1;j<(1<<cnt);j++){
int s=1,sum=0;
for(k=0;k<cnt;k++){
if(j&(1<<k)){
s*=p[i][k];
sum++;
}
}//通过计算sum进行奇加偶减
if(sum%2==1)
res+=num[s];
else
res-=num[s];
}
res=n-res;
if(res>=m)
ans=(ans+b[i]*C(res,m)%MOD)%MOD;
}
printf("%lld\n",ans);
} 
投递大华股份等公司10个岗位
查看5道真题和解析