本來想直接用GCD解決的，后來找了一下，發(fā)現(xiàn)了更好的辦法

歐拉函數(shù) ：
歐拉函數(shù)是數(shù)論中很重要的一個函數(shù)，歐拉函數(shù)是指：對于一個正整數(shù) n ，小于 n 且和 n 互質(zhì)的正整數(shù)（包括 1）的個數(shù)，記作 φ(n) 。

完全余數(shù)集合：
定義小于 n 且和 n 互質(zhì)的數(shù)構(gòu)成的集合為 Zn ，稱呼這個集合為 n 的完全余數(shù)集合。 顯然 |Zn| ＝φ(n) 。

有關(guān)性質(zhì)：
對于素數(shù) p ，φ(p) = p -1 。
對于兩個不同素數(shù) 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) 。

歐拉定理 ：
對于互質(zhì)的正整數(shù) a 和 n ，有 a^φ(n)  ≡ 1 mod n  。

證明：
( 1 ) 令 Zn = {x₁, x₂, ..., x_φ(n)} ， S = {a * x₁ mod n, a * x₂ mod n, ... , a * x_φ(n) mod n} ，
        則 Zn = S 。
        ① 因為 a 與 n 互質(zhì)， x_i (1 ≤ i ≤ φ(n)) 與 n 互質(zhì)， 所以 a * x_i  與 n 互質(zhì)，所以 a * x_i  mod n ∈ Zn 。
        ② 若 i ≠ j ， 那么 x_i ≠ x_j，且由 a, n互質(zhì)可得 a * x_i mod n ≠ a * x_j mod n （消去律）。

( 2 )     a^φ(n) * x₁ * x₂ *... * x_φ(n) mod n
      ≡ (a * x₁) * (a * x₂) * ... * (a * x_φ(n)) mod n
      ≡ (a * x₁ mod n) * (a * x₂ mod n) * ... * (a * x_φ(n) mod n) mod n
      ≡  x₁ * x₂ * ... * x_φ(n) mod n
      對比等式的左右兩端，因為 x_i  (1 ≤ i ≤ φ(n)) 與 n 互質(zhì)，所以 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);
  }
}