欧拉函数

欧拉函数

题目描述

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

输入

一行一个整数N。

输出

一行一个整数φ(N)

样例输入

样例输出

提示

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

对于100%的数据，有N<=2³¹-1

是我的问题，其实这道题并没有想象中的简单orz

首先，这道题其实就是求解一个函数（关于欧拉函数的求解问题，个人推荐一本书《初等数论》，写的确实不错，而关于欧拉函数在其中也具体的做了解释）

那么，我在这里就简单的手推一下：

假定正整数N

∵φ（N）是与其互质的数的数目，显然两个数互质就是不含相同质因子

我们假设N只有两个质因子，将其设为q，p

∵N与不是p，q的倍数的数互质

∴φ（N）=N-N/p-N/q+N/pq

证完

为什么要加N/pq呢？就是因为pq同为q，p的倍数，则在作差时就减了两遍，于是就应该加回来。

因此，由特殊到一般，显然我们可以得到φ（N）=N*（1-1/a）*（1-1/b）......（1-1/n）【n为质因子数目】

显然问题就转化为求最小质因子上，这样就使复杂的问题简单了，至于求最小质因子那么大家应该都会。。。

最后，附上本题代码

 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 }