vijos1629 八（容斥原理

描述

八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。

某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。

格式

输入格式

第一行一个数n，代表不能被整除的数的个数。

第二行n个数，中间用空格隔开。

第三行两个数a，b，中间一个空格。

输出格式

一个整数，为[a,b]间能被8整除却不能被那n个数整除的数的个数。

样例1

样例输入1

3
7764 6082 462
2166 53442

样例输出1

6378

限制

各个测试点1s

提示

对于30%的数据， 1≤n≤5，1≤a≤b≤100000。

对于100%的数据，1≤n≤15，1≤a≤b≤10^9，N个数全都小于等于10000大于等于1。

分析

容斥原理题。
$ans$ans = 用 8 的倍数的个数 - 8的倍数中能被其他数整除的个数 = $\sum (-1{)}^{\mid S\mid -1}\ast (\lfloor \frac{r}{x}\rfloor -\lfloor \frac{l-1}{x}\rfloor )$∑(−1)∣S∣−1∗(⌊xr​⌋−⌊xl−1​⌋)

代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int ans, l, r, n;
int a[16]; 
int gcd(int a, int b){
	return !b? a: gcd(b, a % b);
}
void cal(LL x, int p, int flag){
	int i;
	if(x > r) return;
	ans += flag * (r / x - (l - 1) / x);
	if(p > n) return;
	for(i = p; i <= n; i++) cal(x * a[i] / gcd(x, a[i]), i + 1, -flag);
}
int main(){
	int i, j, m;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d%d", &l, &r);
	cal(8, 1, 1);
	printf("%d", ans);
	return 0;
}