[BZOJ2393] Cirno的完美算数教室（dfs+容斥原理）

传送门

先通过dfs预处理出来所有只有2和9的数，也就大概2000多个。

想在[L,R]中找到是这些数的倍数的数，可以通过容斥原理

那么如果a % b == 0，那么便可以把 a 去掉，因为 b 的倍数肯定包括 a 的倍数，那么就会只剩500多个数

然后我们dfs枚举所有数的可能，并顺便求出他们之间的lcm，选出来的数的个数，如果是奇数就对答案有正的贡献，如果是偶数就对答案有负的贡献

期间如果最小公倍数lcm>R的话就直接return，这个剪枝能省去大部分时间，以至AC

而在[L,R]区间的答案就是ans[1,R] ans[1,L1]

#include <cstdio>#include <algorithm>#define N 10001#define LL long longint n, cnt = 1;LL l, r, ans, f[N], num[N];inline LL gcd(LL x, LL y)inline void dfs(LL v)inline void dfs_again(int i, int c, LL lcm)dfs_again(i + 1, c, lcm);LL tmp = lcm * f[i] / gcd(lcm, f[i]);if(tmp <= r) dfs_again(i + 1, c + 1, tmp);}int main()std::sort(f + 1, f + n + 1);dfs_again(1, 0, 1);printf("%lld\n", ans);return 0;}

上一篇：[luoguP3413] SAC#1 - 萌数（数位DP）

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