Stepan e le coppie#4283

Stepan e le coppie (Editoriale)

Fissiamo $j$ (per esempio $j = 12$ j = 12) e troviamo il numero di tali $i$ per cui $i = M C D (i, 12)$ i = MCD(i, 12). Troviamo i valori di $i$ che soddisfano questa uguaglianza. Questi saranno $i = 1, 2, 3, 4, 6, 12$ i = 1, 2, 3, 4, 6, 12. Cioè, qualsiasi $i$ che sia un divisore di $12$ soddisfa l'uguaglianza $i = M C D (i, 12)$ i = MCD(i, 12).

Il numero di tali $i$ per cui $i = M C D (i, j)$ i = MCD(i, j) è uguale al numero di divisori $d (j)$ del numero $j$ . Poiché $1 \leq j \leq n$ 1 \le j \le n, resta da trovare il numero totale di divisori dei numeri da $1$ a $n$ . Cioè occorre trovare la somma

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

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

Poiché il calcolo di $d (n)$ richiede la fattorizzazione del numero $n$ , il calcolo diretto della somma indicata richiederebbe un tempo $O (n)$ .

Guardiamo alla somma dei divisori in un altro modo. Tra i divisori dei numeri da $1$ a $n$ , l'uno comparirà $⌊ \frac{n}{1} ⌋$ \lfloor{n \over 1}\rfloor volte, il due comparirà $⌊ \frac{n}{2} ⌋$ \lfloor{n \over 2}\rfloor volte e così via (il divisore $i$ comparirà $⌊ \frac{n}{i} ⌋$ \lfloor{n \over i}\rfloor volte). Il numero delle coppie di numeri interi cercate è uguale a

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

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

Questa somma può essere calcolata in un tempo $O (n)$ .

Esempio

Per $n = 6$ n = 6 abbiamo le seguenti coppie:

Il numero di coppie è uguale a

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

Implementazione dell'algoritmo

Leggiamo il valore di $n$ .

scanf("%d",&n);

Calcoliamo la risposta secondo la formula e la stampiamo.

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

Implementazione in Java

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

Implementazione in Python

Leggiamo il valore di $n$ .

n = int(input())

Calcoliamo la risposta secondo la formula e la stampiamo.

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