时间限制: 1 s
空间限制: 1000 KB
题目等级 : 钻石 Diamond
题目描述 Description
输入一个数n,输出小于n且与n互素的整数个数
输入描述 Input Description
包含多组数据,n=0时结束
测试数据组数不会很多,不必先打表后输出
输出描述 Output Description
一组数据一行
样例输入 Sample Input
364684
346
5432
11
24
0
2333333
233333333
0
233333333333333
2333333333333333333333333333333333333333333333333
样例输出 Sample Output
165120
172
2304
10
8
数据范围及提示 Data Size & Hint
1<n<9223372036854775807
n欧拉函数的性质(以下性质中p为素数)
n1、φ(p)=p-1
n2、φ(i*p)=p*φ(i),i%p==0
n3、φ(i*p)=(p-1)*φ(i),i%p!=0
n
n根据以上性质可以得出欧拉函数的线性筛法。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #define lli long long int
7 using namespace std;
8 void read(lli &n)
9 {
10 char c='+';lli x=0;bool flag=0;
11 while(c<'0'||c>'9')
12 {c=getchar();if(c=='-')flag=1;}
13 while(c>='0'&&c<='9')
14 {x=x*10+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 int main()
18 {
19 lli n;lli ans;
20 while(cin>>n)
21 {
22 if(n==0)break;
23 ans=n;
24 if(n%2==0)
25 {
26 while(n%2==0)
27 n=n/2;
28 ans=ans/2;
29 }
30 for(lli i=3;i*i<=n;i+=2)
31 {
32 if(n%i==0)
33 {
34 while(n%i==0) n=n/i;
35 ans=ans/i*(i-1);
36 }
37 }
38 if(n>1)
39 ans=ans/n*(n-1);
40 cout<<ans<<endl;
41 }
42 return 0;
43 }