SPOJ ETF

题目链接：http://www.spoj.com/problems/ETF/

题目大意：求欧拉函数值(Wiki Euler's totient function).

解题思路：参考置顶模板中的筛法求欧拉函数值方法（紫书上的。。。）。

代码：

 1 const int maxn = 1e6 + 5;
 2 int n;
 3 ll phi[maxn];
 4 
 5 void solve(){
 6     memset(phi, 0, sizeof(phi));
 7     phi[1] = 1;
 8     for(int i = 2; i < maxn; i++){
 9         if(!phi[i]){
10             for(int j = i; j < maxn; j += i){
11                 if(phi[j] == 0) phi[j] = j;
12                 phi[j] = phi[j] / i * (i - 1);
13             }
14         }
15     }
16 } 
17 int main(){
18     solve();
19     int t;
20     scanf("%d", &t);
21     while(t--){
22         scanf("%d", &n);
23         printf("%lld
", phi[n]);
24     }
25 }

题目：

ETF - Euler Totient Function

#number-theory #totient

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.

Input

First line contains an integer T, the number of test cases. (T <= 20000)

T following lines, each contains an integer n.

Output

T lines, one for the result of each test case.

Example

Input:
5
1
2
3
4
5

Output:
1
1
2
2
4