SPOJ DCEPCA03

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

题目大意：欧拉函数为totient(n)，请你计算

H=0;
For (i=1; i<=n; i++) {
    For (j=1; j<=n; j++) {
        H = H + totient(i) * totient(j);
    }
}

解题思路：刚开始以为是什么神奇的性质，想了半天也没想出来。用筛法写出来后TLE了，然后发现，这**的就是求个前缀和然后O(n)一遍phi[i] * sum[n]啊。

想多了。。

代码：

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

题目：

DCEPCA03 - Totient Extreme

#math #totient

Given the value of N, you will have to find the value of H. The meaning of H is given in the following code:

H=0; For (i=1; i<=n; i++) { For (j=1; j<=n; j++) { H = H + totient(i) * totient(j); } }

Totient or phi function, φ(n) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1

Constraints

0 < T <= 50
0 < N <= 10^4

Input

The first line contains T, the number of test cases. It is followed by T lines each containing a number N .

Output

For each line of input produce one line of output. This line contains the value of H for the corresponding N.

Example

Input:
2
3
10

Output:
16
1024