题意：

给你一个数n，找出来区间[1,n]内有多少书和n不互质

题解：

容斥原理

这一道题就让我真正了解容斥原理的实体部分 “容斥原理+枚举状态,碰到奇数加上(n-1)/lcm(a,b,c..) 碰到偶数减(n-1)/lcm(a,b,c…)” 这个是lcm(a,b,c,,,)可不是他们的乘积。。

注意了。。。 还有这道题输入会有0

代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 typedef long long ll;
9 const int maxn=100;
10 ll v[maxn],index;
11 ll gcd(ll a,ll b) //求最大公约数
12 {
13 return b==0?a:gcd(b,a%b);
14 }
15 /*
16 当得到a和b的最大公约数d之后, 可以马上得到a和b最小公倍数是(ab)/d.
17 */
18 ll lcm(ll a,ll b) //求最小公倍数
19 {
20 return a/gcd(a,b)*b;
21 }
22 ll get_result(ll n)//容斥原理
23 {
24 ll ans=0;
25 for(ll i=1; i< (1<<index) ; i++)
26 {
27 ll ones=0,mult=1;
28 for(ll j=0; j<index; j++)
29 {
30 if(i & (1<<j))
31 {
32 ones++;
33 mult=lcm(mult,v[j]);
34 }
35 }
36 if(ones&1)//奇数加，偶数减
37 ans+= n/mult;
38 else
39 ans-= n/mult;
40 }
41 return ans;
42 }
43 int main()
44 {
45 ll n;
46 while(~scanf("%lld%lld",&n,&index))
47 {
48 n--;
49 ll flag=0;
50
51 for(ll i=0;i<index;++i)
52 {
53 scanf("%lld",&v[i]);
54 if(v[i]==0)
55 {
56 index--;
57 i--;
58 }
59 else if(!flag && n%v[i]==0) flag=1;
60 }
61 printf("%lld\n",get_result(n));
62
63 }
64 return 0;
65 }