首页 > 代码库 > {容斥原理}

{容斥原理}

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1284

比较基础练一下。

技术分享
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 #define LL long long
 7 const int maxn=100010;
 8 
 9 LL n;
10 int d[4]={2,3,5,7};
11 int main()
12 {
13     while(scanf("%lld",&n)!=EOF)
14     {
15        LL ans=0;
16         for(int i=0;i<16;i++)
17         {
18             int cnt=0;
19             int temp=1;
20             if(i&1)
21             {
22                 temp*=d[0];
23                 cnt++;
24             }
25             if(i&2)
26             {
27                 temp*=d[1];
28                 cnt++;
29             }
30             if(i&4)
31             {
32                 temp*=d[2];
33                 cnt++;
34             }
35             if(i&8)
36             {
37                 temp*=d[3];
38                 cnt++;
39             }
40             if(cnt%2==0)   ans+=n/temp;
41             else  ans-=n/temp;
42         }
43     printf("%lld\n",ans);
44     }
45 }
View Code

 

{容斥原理}