正题

题目链接: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-四元组统计【数论,容斥】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。