【P1813】8的倍数

发表于 | 阅读次数:
字数统计: 622 字

这是一道(很恶心的)数论题，斥容原理的应用， 没很懂实现原理， 来总结一下

原题：

小x最近对数字8很感兴趣，有8进制，2008奥运会之类的。
现在小x想知道，在[x,y]区间里，有多少个数能被8整除。
小y觉得题目太简单，于是给出n个其他数，问在[x,y]区间里，有多少个数能被8整除且不能被这n个数整除。

1≤n≤15，1≤x≤y≤10^9，N个数全都小于等于10^4大于等于1。

思路：

如果要求1 ~ n有多少数可以被8整除， 那么答案直接就是n/8， 但是加上了限定条件被能被a[i]整除。
我们可以把求x ~ y区间内的问题， 转化为分别求出1 ~ x-1 和 1 ~ y 两个区间内的个数， 然后相减。
但是我们需要找出的是在区间内可以被8整除单是不能被a[i]整除的树的个数， 那么我们可以先找出a[i]和8的lcm也就是最小公倍数， 然后直接拿y来除lcm（8， a[i]）
那么我们得到的就是从1到y之间的所有的能够被8整除但是不能被a[i]整除的所有数的个数。比如说16为y a[1] = 16, 那么16和8的lcm 是 16 ， 而且在1 ~ 16之间的能被8整出但是不能被16整除的数字就只有 8 一个了。

在这时我们需要再次使用一下斥容原理， 当我们枚举出这i个数字的选与不选的情况的时候， 我们根据选择的数字的个数的多少来决定答案的个数是加上还是减去。

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) {return (y)?gcd(y,x%y):x;}
ll n, a[20], xx, yy;
bool use[20];
ll ansx, ansy, bowl = 0;
void dfs(int x, int y) {
	if (x>n) {
		ll lcm = 8; int ge = 0;
		for (int i=1;i<=n;++i) if(use[i]){
			lcm*=a[i]/gcd(lcm, a[i]);
			if (lcm>y) break;
			ge++;
		}
		if(ge%2) bowl -= y/lcm;
		else bowl += y/lcm;
		return;
	}
	use[x] = false; dfs(x+1, y);
	use[x] = true; dfs(x+1,y);
}
int main() {
	scanf("%d", &n);
	for (int i=1;i<=n;++i) scanf("%d", &a[i]);
	memset(use, 0, sizeof(use));
	scanf("%d%d", &xx,&yy);
	dfs(1, yy); ansy = bowl;
	bowl = 0;
	dfs(1, xx-1); ansx = bowl; 
	printf("%d\n", ansy - ansx);
	return 0;
}