首页 > 代码库 > Codeforces 803F(容斥原理)

Codeforces 803F(容斥原理)

题意:

给n个正整数,求有多少个GCD为1的子序列。答案对1e9+7取模。

1<=n<=1e5,数字ai满足1<=ai<=1e5

分析:

设f(x)表示以x为公约数的子序列个数

那么ans=f(1)- Σf(pi) + Σf(pi*pj) - Σf(pi*pj*pk) ........

注意到对于一个f(x),它对结果的贡献是:

  若x为合数,那么前面系数为0

  若x由奇数个素数组成,那么系数是-1

  若x由偶数个素数组成,那么系数是1

这明显就是莫比乌斯函数……直接一个线性筛出来

那么问题就是f(x)怎么求,这显然就是f(x)=2^num(x) - 1 (num(x)表示原先序列里有多少个数是x的倍数)

Codeforces 803F(容斥原理)