Longge`s problem (Editorial)

Theorem. If the function $f(n)$ is multiplicative, then the summatory function

is also multiplicative.

Proof. Let x, y \in N, where $x$ and $y$ are coprime.

Let x_1, x_2, ..., x_k be all divisors of $x$, and let y_1, y_2, ..., y_m be all divisors of $y$.

Since $x$ and $y$ are coprime, any divisor x_i is coprime to any divisor y_j. Therefore, GCD(x_i, y_j) = 1. This means that the product x_i \cdot y_j is a divisor of the number x \cdot y.

Moreover, each product x_i \cdot y_j gives a distinct divisor of x \cdot y, and in this way we obtain all divisors of x \cdot y. Therefore, the sum over all divisors of x \cdot y can be represented as a double sum over all pairs of divisors x_i and y_j. Then

Corollary. Consider the function f(n) = GCD(n, c), where $c$ is a constant. Let us show that this function is multiplicative.

If $x$ and $y$ are coprime, then

Therefore, the function f(n) = GCD(n, c) is multiplicative.

Example. Let us compute GCD(36, 90) using the multiplicativity property.

Now let us consider its summatory function:

From the previous theorem, we know that the summatory function of a multiplicative function is also multiplicative. Therefore, the function $g(n)$ is also multiplicative.

If we factor $n$ into powers of prime numbers n = p_1^{a_1} p_2^{a_2}...p_k^{a_k}, then

Lemma. Let $d$ be a divisor of $n$. Then there are exactly $\phi (n/d)$ integers $i$ such that 1 \le i \le n and GCD(i, n) = d.

► If GCD(i, n) = d, then $d$ divides $i$. Let us represent $i$ in the form i = d \cdot j. Since $d$ divides $n$, we can write $n$ as n = d \cdot (n / d). Then:

We are interested in those values of $i$ for which GCD(i, n) = d. Therefore, we must have d \cdot GCD(j, n / d) = d. Hence

The number of integers $j$ that are coprime to $n/d$ is $\phi (n/d)$.

Example. Consider the number n = 24 and find all integers $i$ for which GCD(i, 24) = 3. According to the lemma, the number of such integers is φ(24 / 3) = φ(8) = 4.

To find these integers, let i = 3 \cdot j. Then, from the proof of the lemma, we know that GCD(j, 8) = 1. This equality holds for j \in \{1, 3, 5, 7\}. Therefore, GCD(i, 24) = 3 for i \in \{3, 9, 15, 21\}.

Theorem (formula for the sum of GCDs in terms of Euler’s totient function). Let $n$ be a positive integer and

Then

where the sum is taken over all positive divisors $d$ of $n$, and $\phi$ is Euler's totient function

Proof. Consider all integers $i$ from $1$ to $n$ and group them according to the value of GCD(i, n).

Let GCD(i, n) = e. According to the lemma above, the number of such integers $i$ is exactly $\phi (n/e)$. Each such integer $i$ contributes the same value $e$ to the sum $g(n)$. Therefore, all integers $i$ for which GCD(i, n) = e contribute a total of e \cdot φ(n / e).

The value $e$ is always a divisor of $n$. Therefore, to obtain the entire sum $g(n)$, we need to sum these contributions over all divisors $e$ of $n$:

Let us make a change of variable: d = n / e. Then e = n / d. Since $e$ is a divisor of $n,d$ is also a divisor of $n$. Substituting e = n / d into the obtained formula, we get:

Theorem. Let

Then, for any prime $p$ and positive integer $a$, the following relation holds:

► For a = 1, we have:

For a = 2, we have:

Let us compute g(p^a). The value of GCD(i, p^a) can only be a divisor of p^a. Since $p$ is a prime number, all divisors of p^a have the form p^k, where 0 \le k \le a.

Let us find the number of integers $i$ from $1$ to p^a for which GCD(i, p^a) = p^k. According to the lemma given above, this number is equal to

In addition, for i = p^a we have: GCD(i, p^a) = GCD(p^a, p^a) = p^a.

Therefore

Example. Let n = 6.

Then

At the same time

Let us compute $g(6)$ using the formula g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

Now let us compute $g(6)$ using the multiplicativity of the function f(x) = GCD(x, n):

Example. Let n = 12.

Then

At the same time

Let us compute $g(12)$ using the formula g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}:

The divisors of $12$ are: 1, 2, 3, 4, 6, 12. The number of integers $i$ such that GCD(i, 12) = d is $\varphi (12/d)$. For example, GCD(i, 12) = 3 holds for ϕ(12/3) = ϕ(4) = 2 different values of $i$, namely i = 3, 9.

Now let us compute $g(12)$ using the multiplicativity of the function f(x) = GCD(x, n):

Algorithm implementation

The euler function computes Euler’s totient function.

long long euler(long long n)
{
  long long i, result = n;
  for (i = 2; i * i <= n;i++)
  {
    if (n % i == 0) result -= result / i;
    while (n % i == 0) n /= i;
  }
  if (n > 1) result -= result / n;
  return result;
}

The main part of the program. Read the value of $n$. Compute the value of $g(n)$ using the formula \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right). We look for all divisors of $n$ among the numbers from $1$ to \lfloor \sqrt{n} \rfloor.

If $i$ is a divisor of $n$, then $n/i$ is also a divisor of $n$. Therefore, when we find each divisor i \le \lfloor \sqrt{n} \rfloor, we should add i \phi(\frac{n}{i}) + \frac{n}{i} \phi(i) to the result $res$, taking into account both divisors $i$ and $n/i$.

If $n$ is a perfect square and i = sq = \left\lfloor \sqrt{n} \right\rfloor, then the divisors $i$ and $n/i$ are the same. In this case, iϕ(\frac{n}{i}) = \frac{n}{i} ϕ(i) will be added twice to the sum $res$ as two identical terms. Therefore, subtract one of them from $res$ during the initialization of this variable.

while(scanf("%lld",&n) == 1)
{
  sq = (long long)sqrt(1.0*n);
  res = (sq * sq == n) ? -sq * euler(sq) : 0;

  for (i = 1; i <= sq; i++)
    if(n % i == 0) res = res + i * euler(n/i) + (n / i) * euler(i);
  printf("%lld\n",res);
}

Algorithm implementation – using multiplicativity

Let us factor the number $n$ into prime factors:

We have proved that the function g(n) = \sum_{i=1}^{n} \gcd(i,n) is multiplicative. Therefore

For a power of a prime number, we have proved the following formula:

These are the two formulas used directly in the program.

Process several test cases. Read the value of $n$.

while(scanf("%lld",&n) == 1)
{

In the variable $res$, we'll compute the value of $g(n)$.

  res = 1;

Factor the number $n$ into prime factors. Iterate over possible divisors.

  for (i = 2; i * i <= n; i++)
  {

If the number $i$ is a prime factor, extract the factor p = i^a.

    if (n % i == 0)
    {
      a = 0; p = 1;
      while(n % i == 0)
      {
        a++;
        p *= i;
        n /= i;
      }

Multiply the result $res$ by

      res *= (a + 1) * p - a * p / i;
    }
  }

If n > 1, then $n$ is the last prime factor.

  if (n > 1) res *= (2*n - 1);

Print the answer.

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

Java implementation

import java.util.Scanner;

public class Main
{
  static long euler(long n)
  {
    long result = n;
    for(int i = 2; i <= Math.sqrt(n);i++)
    {
      if (n % i == 0) result -= result / i;
      while (n % i == 0) n /= i;
    }
    if (n > 1) result -= result / n;
    return result;
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      long n = con.nextLong();
      long sq = (long)Math.sqrt(n);
      long res = (sq * sq == n) ? -sq * euler(sq) : 0;
      for(long i = 1; i <= sq; i++)
        if (n % i == 0)
          res = res + i * euler(n/i) + (n / i) * euler(i);
      System.out.println(res);
    }
    con.close();
  }
}