12914. Totient Extreme

 

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.

 

Input. The first line contains the number of test cases t (0 < t ≤ 50). It is followed by t lines each containing a number n (0 < n ≤ 104).

 

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

 

Sample Input

Sample Output

2

3

10

16

1024

 

 

РЕШЕНИЕ

Функция Эйлера

 

Анализ алгоритма

Перепишем указанную сумму H следующим образом:

φ(1) * φ(1) + φ(1) * φ(2) + … φ(1) * φ(n) +

φ(2) * φ(1) + φ(2) * φ(2) + … φ(2) * φ(n) +

. . .

φ(n) * φ(1) + φ(n) * φ(2) + … φ(n) * φ(n)  =

 

φ(1) * (φ(1) + φ(2) + … φ(n)) +

φ(2) * (φ(1) + φ(2) + … φ(n)) +

. . .

φ(n) * (φ(1) + φ(2) + … φ(n)) =

 

= (φ(1) + φ(2) + … φ(n))2

Реализуем решето, которое вычислит все значения функции Эйлера от 1 до 104 и занесет их в массив fi. Заполним массив частичных сумм ps[i] = φ(1) + φ(2) + … φ(i). Далее для каждого входного значения n выведем ps[n] * ps[n].

 

Реализация алгоритма

 

#include <stdio.h>

#define MAX 10001

 

long long fi[MAX], ps[MAX], res;

int tests, n;

 

void FillEuler(void)

{

  int i, j;

  fi[0] = fi[1] = 0;

  for(i = 2; i < MAX; i++)

    if(!fi[i])

      for(j = i; j < MAX; j += i)

      {

        if(!fi[j]) fi[j] = j;

        fi[j] -= fi[j]/i;

      }

 

  ps[0] = 0; ps[1] = 1;

  for(i = 2; i < MAX; i++)

    ps[i] = ps[i-1] + fi[i];

}

 

int main(void)

{

  FillEuler();

  scanf("%d",&tests);

  while(tests--)

  {

    scanf("%d",&n);

    res = ps[n] * ps[n];

    printf("%lld\n",res);

  }

  return 0;

}