Educational Codeforces Round 20 F. Coprime Subsequences（容斥）

本文主要是介绍Educational Codeforces Round 20 F. Coprime Subsequences（容斥），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：http://codeforces.com/contest/803/problem/F

题解：

f[i]表示最大公约数为i的子序列的个数，我们可以求出所有公约数为i的倍数的子序列的个数，然后从后向前扫，对于每一个i，减去公约数为ki的（k>=2）的子序列的个数，最后可以得到答案。注意处理空集的情况。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
typedef long long ll;
ll f[MAXN],sv[MAXN],po[MAXN];
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n,mx=0;scanf("%d",&n);po[0]=1;for(int i=1;i<MAXN;i++){po[i]=(po[i-1]*2)%MOD;}for(int i=1;i<=n;i++){int x;scanf("%d",&x);sv[x]++;}for(int i=1;i<MAXN;i++){f[i]=1;for(int j=i;j<MAXN;j+=i){f[i]=(f[i]*po[sv[j]])%MOD;}f[i]-=1;}for(int i=MAXN-1;i>=1;i--){for(int j=i+i;j<MAXN;j+=i){f[i]=(f[i]-f[j]+MOD)%MOD;}}printf("%lld\n",f[1]);return 0;
}

这篇关于Educational Codeforces Round 20 F. Coprime Subsequences（容斥）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---