容斥原理--简单应用

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

7
12
0

Sample Output

6
4

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

模板：

#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;
}

最后

以上就是内向小霸王为你收集整理的容斥原理--简单应用的全部内容，希望文章能够帮你解决容斥原理--简单应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。