Stepan and pairs#4283

Stepan and pairs (Editorial)

Let's fix $j$ (for example $j = 12$ j = 12) and find the number of $i$ such that $i = GC D (i, 12)$ i = GCD(i, 12).

The values of $i$ that satisfy this equation are $i = 1, 2, 3, 4, 6, 12$ i = 1, 2, 3, 4, 6, 12. So, any $i$ that is a divisor of $12$ satisfies the equation $i = GC D (i, 12)$ i = GCD(i, 12).

The number of such $i$ for which $i = GC D (i, j)$ i = GCD(i, j) is equal to the number of divisors $d (j)$ of $j$ . Since $1 \leq j \leq n$ 1 \le j \le n, we need to find the count of all divisors of numbers from $1$ to $n$ . In other words, we need to find the sum

d (1) + d (2) + ... + d (n)

d(1) + d(2) + ... + d(n)

However, calculating $d (n)$ requires factoring the number $n$ , so direct computation of this sum takes $O (n)$ time.

Let's look at the sum of divisors in a different way. Among the divisors of numbers from $1$ to $n$ , one appears $⌊ \frac{n}{1} ⌋$ \lfloor{n \over 1}\rfloor times, two appears $⌊ \frac{n}{2} ⌋$ \lfloor{n \over 2}\rfloor times, and so on (the divisor $i$ appears $⌊ \frac{n}{i} ⌋$ \lfloor{n \over i}\rfloor times). The number of required pairs of integers is

i = 1 \sum n ⌊ \frac{n}{i} ⌋

\sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor

This sum can be computed in $O (n)$ time.

Example

For $n = 6$ n = 6 we have the next pairs:

The number of pairs is

6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 = = 6 + 3 + 2 + 1 + 1 + 1 = 14

6 / 1 + 6 / 2 + 6 / 3 + 6 / 4 + 6 / 5 + 6 / 6 = \\ = 6 + 3 + 2 + 1 + 1 + 1 = 14

Algorithm implementation

Read the value of $n$ .

scanf("%d",&n);

Compute the answer using the formula and print it.

s = 0;
for (i = 1; i <= n; i++)
  s += n / i;
printf("%d\n",s);

Java implementation

import java.util.*;

class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int s = 0;
    for(int i = 1; i <= n; i++)
      s += n / i;
    System.out.println(s);
    con.close();
  }
}

Java

Python implementation

Read the value of $n$ .

n = int(input())

Compute the answer using the formula and print it.

s = 0
for i in range(1,n+1):
  s += n // i
print(s)