首页 > 其他 > 详细

欧拉函数

时间:2018-12-15 18:32:17      阅读:139      评论:0      收藏:0      [点我收藏+]

欧拉函数

题目描述

对正整数nn的欧拉函数(即φ(N))是少于或等于n的数中与n互质的数的数目。例如φ(8)=4,因为1,3,5,7均和8互质。

输入

一行一个整数N。

输出

一行一个整数φ(N)

样例输入

8

样例输出

4

提示

对于70%的数据,有N<=1000

对于100%的数据,有N<=231-1

PS:由于这道题确实不难,并且在模拟的时候也开了longlong,所以这里直接搬题解代码qwq

这道题很显然就是求出小于等于x的数中与x互质的数的数量,那么我们应该立刻意识到分类讨论这件事,但是发现并没有什么用,辗转相除法完美的解决了它orz(PS:还有一种算法叫更相减损术,由于没有gcd来的快,并且不易理解,这里不多加介绍)

由于辗转相除极大的优化了时间复杂度,那么我们就不用考虑其他的算法优化了,只要依次枚举判断即可。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 long long n,ans;
 5 int main()
 6 {
 7     cin>>n;
 8     ans=n;
 9     int i=1;
10     while(n!=1)
11     {
12         i++;
13         if(n%i==0)
14         {
15             ans=ans/i*(i-1);
16             n=n/i;
17         }
18         while(n%i==0) n=n/i;
19     }
20     cout<<ans;
21     return 0;
22 }

欧拉函数

原文:https://www.cnblogs.com/yufenglin/p/10124146.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!