本来想直接用GCD解决的,后来找了一下,发现了更好的办法

欧拉函数 :
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。

完全余数集合:
定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为 n 的完全余数集合。 显然 |Zn| =φ(n) 。

有关性质:
对于素数 p ,φ(p) = p -1 。
对于两个不同素数 p, q ,它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1)  。
这是因为 Zn = {1, 2, 3,  ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} , 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1)  =φ(p) * φ(q)

欧拉定理 :
对于互质的正整数 a 和 n ,有 aφ(n)  ≡ 1 mod n  。

证明:
( 1 ) 令 Zn = {x1, x2, ..., xφ(n)} S = {a * x1 mod n, a * x2 mod n, ... , a * xφ(n) mod n}
        则 Zn = S 。
        ① 因为 a 与 n 互质, xi (1 ≤ i ≤ φ(n)) 与 n 互质, 所以 a * xi  与 n 互质,所以 a * xi  mod n ∈ Zn 。
        ② 若 i ≠ j , 那么 xixj,且由 a, n互质可得 a * xi mod n ≠ a * xj mod n (消去律)。

( 2 )     aφ(n) * x1 * x2 *... * xφ(n) mod n
     
(a * x1) * (a * x2) * ... * (a * xφ(n)) mod n
      
(a * x1 mod n) * (a * x2 mod n) * ... * (a * xφ(n) mod n) mod n
     
  x1 * x2 * ... * xφ(n) mod n
      对比等式的左右两端,因为
xi  (1 ≤ i ≤ φ(n)) 与 n 互质,所以 aφ(n)  ≡  1 mod n (消去律)。
注:
消去律:如果 gcd(c,p) = 1 ,则 ac ≡ bc mod p ⇒ a ≡ b mod p 。


代码如下:

 

import java.util.*;
import java.io.*;

public class Solution 
{
  
public static void main (String[] argv) throws IOException
  
{
    BufferedReader in 
= new BufferedReader(new InputStreamReader(System.in));
 StringTokenizer st 
= new StringTokenizer(in.readLine());
    
int n = Integer.parseInt(st.nextToken());
    
double j = n;
    
for (int i = 2; i <= n;i++)
     
if (n%i==0)
     
{
      j 
= j * (1 - 1/(double)i);
      
while (n%i==0
       n 
= n / i;    
     }

    System.out.println((
int)j);
  }

}