Totient Extreme#4107
Sign in

Totient Extreme (Editorial)

Rewrite the given sum as follows:

φ(1) \cdot φ(1) + φ(1) \cdot φ(2) + ... + φ(1) \cdot φ(n) + \\ φ(2) \cdot φ(1) + φ(2) \cdot φ(2) + ... + φ(2) \cdot φ(n) + \\ . . . \\ φ(n) \cdot φ(1) + φ(n) \cdot φ(2) + ... + φ(n) \cdot φ(n)

Group the terms in the sum by their common factor:

φ(1) \cdot (φ(1) + φ(2) + … φ(n)) + \\ φ(2) \cdot (φ(1) + φ(2) + … φ(n)) + \\ . . . \\ φ(n) \cdot (φ(1) + φ(2) + … φ(n))

The same factor appears in all terms. Factor it out:

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

Implement a sieve that computes all values of Euler's totient function from to 10^4 and stores them in the array. Then, build an array of partial sums , where

sum[i] = φ(1) + φ(2) + ... + φ(i)

After that, for each input value , print the product

sum[n] \cdot sum[n]

Example

Consider the state of the array containing the values of Euler's totient function and the array containing the partial sums:

For n = 10, the answer is

(φ(1) + φ(2) + … φ(10))^2 = sum[10]^2 = 32^2 = 1024

Algorithm implementation

Declare the arrays and , where:

#define MAX 10001
long long fi[MAX], sum[MAX];

The FillEuler function fills the array with the values of Euler's totient function:

fi[i] = φ(i)~for~all~1 ≤ i < MAX 
void FillEuler(void)
{
  int i, j;
  for (i = 0; i < MAX; i++) fi[i] = i;
  for (i = 2; i < MAX; i++)
    if (fi[i] == i)
      for (j = i; j < MAX; j += i)
        fi[j] -= fi[j] / i;
C++

Compute the partial sums . Initialize the first elements of the array.

  sum[0] = 0; sum[1] = 1;

Then, compute the remaining partial sums sequentially.

  for(i = 2; i < MAX; i++)
    sum[i] = sum[i-1] + fi[i];
}

The main part of the program. Fill the and arrays.

FillEuler();

Process test cases:

scanf("%d",&tests);
while(tests--)
{
  scanf("%d",&n);

For each input value , compute and print the answer

sum[n] \cdot sum[n] = (φ(1) + φ(2) + … φ(n))^2 
  res = sum[n] * sum[n];
  printf("%lld\n",res);
}