#笔记 欧拉函数
在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。
φ函数的值 Euler函数 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) 其中p1, p2……pn为x的所有质因数，x是不为0的整数
例如：
φ（10）=10×（1－1/2）×（1－1/5）=4
φ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8
φ（49）=49×（1－1/7）=42
性质：
1) pk的欧拉函数 对于给定的一个素数p，我们知道φ(p) = p-1。 假设一个整数n是p的k次幂，也就是 n = pk，k∈N+ 容易证明
证明： 已知小于 的正整数个数为
-1个， 和pk不互质的正整数有{p×1,p×2,...,p×(
-1)}共计
-1个 所以φ(n) =
-1 - (
-1) =
- pk-1
例如：
比32小的数有31个， 2的倍数有2×1, 2×2, ..., 2×15
所以φ(32)=31-15=16
2 ) pq的欧拉函数 假设p,q是两个互质的正整数，则pq的欧拉函数为 φ(pq) = φ(p)φ(q)，gcd(p,q)=1
3) 任意正整数的欧拉函数 φ(n)=n∏(1-1/p)=n∏( ( p - 1)/p )，其中p为能够被n整除的质数
[ 其他的没有写出 ]
例题
描述
给定 n，一个正整数，有多少个小于 n 的正整数是 n 的相对素数？如果没有整数 x > 1、y > 0、z > 0，则两个整数 a 和 b 是相对素数，
使得 a = xy 和 b = xz。
输入
有几个测试用例。对于每个测试用例，标准输入包含 n <= 1，000，000，000 的行。最后一个情况后面跟着包含 0 的行。
输出
对于每个测试用例，应该有一行输出来回答上面提出的问题。
示例输入
7
12
0
示例输出
6
4
#include<iostream>
using namespace std;
typedef long long ll;ll OL(ll );
ll Fast_pow(ll base, ll power);int main(){ll n,ans=1;while((cin>>n)&&(n!=0)){if(n!=1)ans=OL(n);cout<<ans<<endl; }return 0;
}
ll Fast_pow(ll base ,ll power){ //快速幂算法 ll result=1;while(power>0){if(power&1){result*=base;}power >>= 1;base=base*base;}return result;
}// φ(n) = pk - pk-1
ll OL(ll n ){ll i=2,arr[40010][2]={0},cnt=0,ans=1; //arr数组用来存储n的质因数while(n/i){ //求n的所有质因数 if(n%i==0){arr[cnt][0]=i; while(n%i==0){n/=i;arr[cnt][1]++;}cnt++;}i++;}for(i=0;arr[i][0]!=0;i++){ans*=(arr[i][0]-1)*Fast_pow(arr[i][0],arr[i][1]-1); //欧拉函数 }return ans;
}//另一种写法 φ(n)=n*∏(1-1/p)=n*∏( ( p - 1)/p ) p为n的各个质因数 //ll OL( ll n ){
// ll i=2,ans=n;
// for( i=2; i*i<=n; i++){ //一个一个寻找n的质因数，如果n是质数的话不会包括n
// if( n%i == 0){
// ans=ans/i*(i-1); //先除再乘是为了防止出现错误（先乘再除会出现浮点数）
// while(n%i == 0)
// n/=i;
// }
// }
// if(n>1){ //n本身是个质数，n是它本身的质因数
// ans=ans/n*(n-1);
// }
// return ans;
//}