[luoguP3172] [CQOI2015]选数（递推+容斥原理）

传送门

不会莫比乌斯反演，不会递推。

但是我会看题解。

先将区间[L,H]变成(L1,H]，这样方便处理

然后求这个区间内gcd为k的方案数

就是求区间((L1)/k,H/k]中gcd为1的方案数

有个重要的性质：如果有一些不相同的数，最大的为a，最小的为b，任意选取其中的一些数，则他们的gcd<=ab

设f[i]表示gcd为i且所选的数不相同的方案数，但是不好求，只容易求出gcd为i的倍数g[i]的方案数

考虑容斥原理，f[i] = g[i] f[2i] f[3i] ……

计算g[i]的时候要把相同的数的方案数减去，因为我们有个前提，只有数都不相同时gcd的大小才能保证

倒着递推便可以省略g数组

#include <cstdio>#define N 100001#define p 1000000007#define LL long longusing namespace std;LL f[N];int n, k, l, r, flag, len;inline LL ksm(LL x, int y)return ret;}int main()printf("%lld\n", (f[1] + flag + p) % p);return 0;}

上一篇：[luoguP4035] [JSOI2008]球形空间产生器（高斯消元）

下一篇：[luoguP1053] 篝火晚会（贪心 + 乱搞）