51nod--1136 欧拉函数(0级算法题)

51nod–1136 欧拉函数

基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。
Input
输入一个数N。(2 <= N <= 10^9)
Output
输出Phi(n)。
Input示例
8
Output示例
4

/* 根据唯一分解定理：任意正整数都可以唯一的表示为多个素数的幂相乘 解题思路：根据公式&(n) = n*(1-1/p1)...(1-1/pk) 其中pi代表就是那**素因子**，记住这个公式吧，之前是根据容斥定理得到的 */
code：
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(euler_phi(n));
    }
    public static int euler_phi(int n ){
        int m = (int) Math.sqrt(n+0.5);
        int ans =n;
        for(int i=2; i<=m; ++i)
            if(n%i == 0){ //第一个一定是素因子
            //为什么呢？首先能取模为0，表示是因子，
            //其次这里的i相当于是p，是根据唯一分解定理来
            //说，都是素数
                ans = ans / i * (i-1);
                //while是将指数弄到0
                while(n % i == 0)
                    n /= i;
            }
        if(n > 1)
            ans = ans / n * (n-1);
        return ans;
    }
}