題目鏈接：點擊查看

題目大意：先拋出公質數的定義，若數 num 與 m 個數都互質，則稱 num 為 m 個數的 m元公質數 ，現在給出 n 個數和 m ，需要求出任意 m 個數的所有 m 元公質數(要求公質數也在這 n 個數中)之和

題目分析：讀完題后可能有點迷茫，但是仔細分析一下發現并不難，首先 m元公質數 要求 m 個數與其互質，且這個公質數也要在 n 個數之中，不難想到可以枚舉這 n 個數作為這個 m元公質數，然后計算出有多少個數與其互質，既然題目需要選出 m 個數，那就是 C( num , m ) 了，num 是與當前枚舉的數所互質的數的個數，C( num , m ) 的意思是有多少組數可以選擇當前枚舉的數作為 m元公質數，既然讓求和，再乘上這個數就行了

關于怎么求出有多少個數與某個數互質，可以參考 HDU4135 ， 容斥原理的經典例題，套上模板就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;const int mod=998244353;LL fac[N],inv[N],a[N],cnt[N];vector<int>p[N];LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }LL C(int n,int m) {if(m>n)return 0;return fac[n]*inv[n-m]%mod*inv[m]%mod; }void solve(int pos,LL val) {for(int i=1;i*i<=val;i++)//因數分解 if(val%i==0){cnt[i]++;if(i!=val/i)cnt[val/i]++;}for(int i=2;i*i<=val;i++)//質因子分解if(val%i==0){while(val%i==0)val/=i;p[pos].push_back(i);}if(val!=1)p[pos].push_back(val); }void init() {fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;inv[N-1]=q_pow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",a+i);solve(i,a[i]);}LL ans=0;for(int i=1;i<=n;i++)//枚舉a[i]，計算與a[i]互質的有幾個數{LL num=0;for(int k=1;k<(1<<p[i].size());k++){LL tot=0;LL mul=1;for(int j=0;j<p[i].size();j++){if(k&(1<<j)){tot++;mul*=p[i][j];}}if(tot&1)//奇加偶減 num+=cnt[mul];elsenum-=cnt[mul];}num=n-num;ans=(ans+a[i]*C(num,m))%mod;}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 小朋友你是否有很多问号(容斥+组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。