正題

題目鏈接:https://www.luogu.com.cn/problem/P2714

---

題目大意

給出$n$個數，求有多少個$(i,j,k,l)$使得$gcd(a_i,a_j,a_k,a_l)=1$。

---

解題思路

我們設$f_i$表示$gcd$和為$i$的方案數。$F_i$表示$gcd$和為$i$的倍數的方案數。

先考慮如何統計$F_i$，其實就是選出$4$個$i$的倍數的方案數，可以統計$i$的倍數的個數即可計算。

然后有$$f_i=F_i?\sum _{i|j}{f}_j$$

時間復雜度$O(Tn\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=11000; ll n,f[N]; int main() {while(scanf("%lld",&n)!=EOF){memset(f,0,sizeof(f));for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);f[x]++;}for(ll i=1;i<N;i++)for(ll j=i<<1;j<N;j+=i)f[i]+=f[j];for(ll i=N-1;i>=1;i--){f[i]=f[i]*(f[i]-1)*(f[i]-2)*(f[i]-3)/24;for(ll j=2*i;j<N;j+=i)f[i]-=f[j];}printf("%lld\n",f[1]);} }

總結

以上是生活随笔為你收集整理的P2714-四元组统计【数论,容斥】的全部內容，希望文章能夠幫你解決所遇到的問題。

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