首页 > 代码库 > 4939 欧拉函数

4939 欧拉函数

2024-10-14 14:59:39   217人阅读

 时间限制: 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 }

 

4939 欧拉函数


联系
我们