（newcoder 15079）无关（容斥原理）

题目链接：登录—专业IT笔试面试备考平台_牛客网

样例1输入：

1 10 4
2 3 5 7

样例1输出：

1

样例2输入：

2 10 4
2 3 5 7

样例2输出：

0

分析：求区间[L,R]内与集合A无关的正整数的个数我们可以转化为求[1,R]内与集合A无关的正整数的个数减去[1,L-1]内与集合A无关的正整数的个数

下面给出区间[1,n]中与集合A无关的正整数个数的求法

设性质Ai为可以被ai整除
则我们要求的问题就是N((1-A1)(1-A2)……(1-An))

由容斥原理得：

 直接套公式求解即可：

下面是代码，注意剪枝：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
long long a[1003];
long long lcm(long long a,long long b)
{
	return a/__gcd(a,b)*b;
}
long long solve(long long n,int k)
{
	long long ans=0;
	for(int i=0;i<1<<k;i++)//暴力枚举所有情况 
	{
		long long sign=1,t=1;
		for(int j=0;j<k;j++)
		{
			if(i>>j&1)
			{
				sign*=-1;
				t=lcm(t,a[j]);
				if(t>n) break;//注意剪枝 
			}
		}
		ans+=sign*(n/t);
	}
	return ans;
}
int main()
{
	long long l,r;
	int k;
	cin>>l>>r>>k;
	for(int i=0;i<k;i++)
		cin>>a[i];
	printf("%lld\n",solve(r,k)-solve(l-1,k));
	return 0;
}