我是靠谱客的博主 内向小霸王,这篇文章主要介绍容斥原理--简单应用,现在分享给大家,希望可以做个参考。

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

复制代码
1
2
3
7 12 0

Sample Output

复制代码
1
2
6 4

问题:求1到n之间有多少个数与n互质。

模板:

复制代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream> #include<vector> using namespace std; typedef long long ll; ll solve(ll n,ll r)//求1到r有多少个元素与n互质 { vector<ll>vc;//假设n=r=28; for(ll i=2;i*i<n;i++) //5<sqrt(n)<6 { if(n%i==0) { vc.push_back(i); while(n%i==0) { n/=i; } } } if(n>1) vc.push_back(n);//vc={2,7},sqrt(n)之前的因子,sqrt(n)之后剩余无法被取余的; ll ans=0; for(ll i=1;i<(1<<vc.size());i++)//vc.size()=2 1<<2 = 2^2 = 4 { ll mul=1,bits=0; for(ll j=0;j<vc.size();j++)//vc.size()=2 { if(i&(1<<j))//判断第几个因子被用到 1<<j =2^j { bits++; mul*=vc[j]; // i 1 2 3 } // j 0 1 0 1 0 1 } //i&(1<<j) 1 0 0 2 1 2 ll cur=r/mul; // bits 1 0 0 1 1 2 if(bits&1) ans+=cur; // mul 2 7 2 2*7 else ans-=cur; // cur 14 4 2 } // ans 14 14+4 14+4-2 return r-ans; //28-(14+4-2)=12 } int main() { ll n; while(cin>>n&&n) { cout<<solve(n,n)<<endl; } return 0; }

 

最后

以上就是内向小霸王最近收集整理的关于容斥原理--简单应用的全部内容,更多相关容斥原理--简单应用内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(67)

评论列表共有 0 条评论

立即
投稿
返回
顶部