Il problema di Longge (Editoriale)

Teorema. Se la funzione $f (n)$ è moltiplicativa, allora la funzione sommatoria

S_{f} (n) = d ∣ n \sum f (d)

S_f(n) = \sum_{d \mid n} f(d)

è anch'essa moltiplicativa.

► Siano $x, y \in N$ x, y \in N, con $x$ e $y$ coprimi.

Siano $x_{1}, x_{2}, ..., x_{k}$ x_1, x_2, ..., x_k — tutti i divisori di $x$ , e $y_{1}, y_{2}, ..., y_{m}$ y_1, y_2, ..., y_m — tutti i divisori di $y$ .

Poiché $x$ e $y$ sono coprimi, ogni divisore $x_{i}$ x_i è coprimo con ogni divisore $y_{j}$ y_j. Quindi $M C D (x_{i}, y_{j}) = 1$ MCD(x_i, y_j) = 1. Ciò significa che il prodotto $x_{i} \cdot y_{j}$ x_i \cdot y_j è un divisore del numero $x \cdot y$ x \cdot y.

Inoltre, ogni prodotto $x_{i} \cdot y_{j}$ x_i \cdot y_j fornisce un divisore distinto del numero $x \cdot y$ x \cdot y, e in questo modo otteniamo tutti i divisori del numero $x \cdot y$ x \cdot y. Di conseguenza, la somma su tutti i divisori del numero $x \cdot y$ x \cdot y può essere rappresentata come una doppia somma su tutte le coppie di divisori $x_{i}$ x_i e $y_{j}$ y_j. Allora

S_{f} (x) \cdot S_{f} (y) = i = 1 \sum k f (x_{i}) \cdot j = 1 \sum m f (y_{j}) = i, j \sum f (x_{i}) f (y_{j}) = i, j \sum f (x_{i} y_{j}) = S_{f} (x y)

S_f(x) \cdot S_f(y) = \sum_{i=1}^{k} f(x_i) \cdot \sum_{j=1}^{m} f(y_j) = \sum_{i,j} f(x_i)f(y_j) = \sum_{i,j} f(x_i y_j) = S_f(xy)

Corollario. Consideriamo la funzione $f (n) = M C D (n, c)$ f(n) = MCD(n, c), dove $c$ — è una costante. Mostriamo che questa funzione è moltiplicativa.

Se $x$ e $y$ sono coprimi, allora

f (x \cdot y) = M C D (x \cdot y, c) = M C D (x, c) \cdot M C D (y, c) = f (x) \cdot f (y)

f(x \cdot y) = MCD(x \cdot y, c) = MCD(x, c) \cdot MCD(y, c) = f(x) \cdot f(y)

Di conseguenza la funzione $f (n) = M C D (n, c)$ f(n) = MCD(n, c) è moltiplicativa.

Esempio. Calcoliamo $M C D (36, 90)$ MCD(36, 90) utilizzando la proprietà di moltiplicatività.

M C D (36, 90) = M C D (4 \cdot 9, 90) = M C D (4, 90) \cdot M C D (9, 90) = 2 \cdot 9 = 18

MCD(36, 90) = MCD(4 \cdot 9, 90) = MCD(4, 90) \cdot MCD(9, 90) = 2 \cdot 9 = 18

Ora consideriamo la sua funzione sommatoria:

g (n) = i = 1 \sum n g cd (i, n)

g(n) = \sum_{i=1}^{n} \gcd(i,n)

Dal teorema precedente sappiamo che la funzione sommatoria di una funzione moltiplicativa è anch'essa moltiplicativa. Di conseguenza, anche la funzione $g (n)$ è moltiplicativa.

Se scomponiamo $n$ in potenze di numeri primi $n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}$ n = p_1^{a_1} p_2^{a_2}...p_k^{a_k}, allora

g (n) = g (p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}) = g (p_{1}^{a_{1}}) \cdot g (p_{2}^{a_{2}}) \cdot ... \cdot g (p_{k}^{a_{k}})

g(n) = g(p_1^{a_1} p_2^{a_2}...p_k^{a_k}) = g(p_1^{a_1}) \cdot g(p_2^{a_2}) \cdot ... \cdot g(p_k^{a_k})

Lemma. Sia $d$ — un divisore del numero $n$ . Allora esistono esattamente $φ (n / d)$ numeri $i$ tali che $1 \leq i \leq n$ 1 \le i \le n e $M C D (i, n) = d$ MCD(i, n) = d.

► Se $M C D (i, n) = d$ MCD(i, n) = d, allora $d$ divide $i$ . Rappresentiamo il numero $i$ nella forma $i = d \cdot j$ i = d \cdot j. Poiché $d$ divide $n$ , il numero $n$ può essere scritto nella forma $n = d \cdot (n / d)$ n = d \cdot (n / d). Allora:

M C D (i, n) = M C D (d \cdot j, n) = M C D (d \cdot j, d \cdot (n / d)) = d \cdot M C D (j, n / d)

MCD(i, n) = MCD(d \cdot j, n) = MCD(d \cdot j, d \cdot (n / d)) = d \cdot MCD(j, n / d)

Ci interessano quegli $i$ per cui $M C D (i, n) = d$ MCD(i, n) = d. Pertanto deve valere $d \cdot M C D (j, n / d) = d$ d \cdot MCD(j, n / d) = d. Da ciò segue

M C D (j, n / d) = 1

MCD(j, n / d) = 1

Il numero di valori $j$ coprimi con $n / d$ è pari a $φ (n / d)$ .

Esempio. Consideriamo il numero $n = 24$ n = 24 e troviamo tutti i numeri $i$ per cui $M C D (i, 24) = 3$ MCD(i, 24) = 3. Secondo il lemma, il numero di tali valori è pari a $φ (24/3) = φ (8) = 4$ φ(24 / 3) = φ(8) = 4.

Per trovare questi numeri, rappresentiamo $i = 3 \cdot j$ i = 3 \cdot j. Allora dalla dimostrazione del lemma segue che deve valere $M C D (j, 8) = 1$ MCD(j, 8) = 1. L'uguaglianza vale per $j \in {1, 3, 5, 7}$ j \in \{1, 3, 5, 7\}. Di conseguenza, $M C D (i, 24) = 3$ MCD(i, 24) = 3 for $i \in {3, 9, 15, 21}$ i \in \{3, 9, 15, 21\}.

Teorema.

g (n) = i = 1 \sum n g cd (i, n) = n d ∣ n \sum \frac{φ ( d )}{d}

g(n) = \sum_{i=1}^{n} \gcd(i,n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

► Consideriamo tutti i numeri $i$ da $1$ a $n$ e raggruppiamoli in base al valore di $M C D (i, n)$ MCD(i, n).

Sia $M C D (i, n) = e$ MCD(i, n) = e. Secondo il lemma sopra riportato, il numero di tali valori $i$ è esattamente $φ (n / e)$ . Ogni valore $i$ di questo tipo contribuisce alla somma $g (n)$ con lo stesso valore, pari a $e$ . Pertanto tutti i numeri $i$ per cui $M C D (i, n) = e$ MCD(i, n) = e forniscono insieme un contributo pari a $e \cdot φ (n / e)$ e \cdot φ(n / e).

Il valore $e$ è sempre un divisore del numero $n$ . Perciò, per ottenere l'intera somma $g (n)$ , è necessario sommare questi contributi su tutti i divisori $e$ del numero $n$ :

g (n) = e ∣ n \sum e φ (\frac{n}{e})

g(n) = \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right)

Effettuiamo un cambio di variabile: $d = n / e$ d = n / e. Allora $e = n / d$ e = n / d. Poiché $e$ è un divisore di $n$ , anche il numero $d$ è un divisore di $n$ . Sostituendo $e = n / d$ e = n / d nella formula ottenuta, otteniamo:

g (n) = e ∣ n \sum e φ (\frac{n}{e}) = d ∣ n \sum \frac{n}{d} φ (d) = n d ∣ n \sum \frac{φ ( d )}{d}

g(n) = \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right) = \sum_{d \mid n} \frac{n}{d}\varphi(d) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

Teorema. Sia

g (n) = i = 1 \sum n g cd (i, n)

g(n) = \sum_{i=1}^{n} \gcd(i,n)

Allora per ogni numero primo $p$ e naturale $a$ vale la relazione:

g (p^{a}) = (a + 1) p^{a} - a p^{a -1}

g(p^a) = (a + 1)p^a - ap^{a–1}

► Per $a = 1$ a = 1 abbiamo:

g (p) = M C D (1, p) + M C D (2, p) + ... + M C D (p, p) = (p - 1) + p = 2 p - 1

g(p) = MCD(1, p) + MCD(2, p) + ... + MCD(p, p) = (p - 1) + p = 2p - 1

Per $a = 2$ a = 2, abbiamo:

= (1 + 1 + \dots + 1 + p) + (1 + 1 + \dots + 1 + p) + ... (1 + 1 + \dots + 1 + p^{2}) =

= (1 + 1 + … + 1 + p) + \\ (1 + 1 + … + 1 + p) + \\ ... \\ (1 + 1 + … + 1 + p^2) =

= (p - 1 + p) \cdot (p - 1) + (p - 1 + p^{2}) = (2 p - 1) \cdot (p - 1) + (p^{2} + p - 1) = 2 p^{2} - 2 p - p + 1 + (p^{2} + p - 1) = = 3 p^{2} - 2 p

= (p - 1 + p) \cdot (p - 1) + (p - 1 + p^2) = \\ (2p - 1) \cdot (p - 1) + (p^2 + p - 1) = \\ 2p^2 - 2p - p + 1 + (p^2 + p - 1) = \\ = 3p^2 - 2p

Calcoliamo $g (p^{a})$ g(p^a). Il valore $M C D (i, p^{a})$ MCD(i, p^a) può essere soltanto un divisore del numero $p^{a}$ p^a. Poiché $p$ — è un numero primo, tutti i divisori di $p^{a}$ p^a hanno la forma $p^{k}$ p^k, dove $0 \leq k \leq a$ 0 \le k \le a.

Troviamo il numero di valori $i$ da $1$ a $p^{a}$ p^a per cui $M C D (i, p^{a}) = p^{k}$ MCD(i, p^a) = p^k. Secondo il lemma sopra riportato, questo numero è pari a

φ (p^{a - k}) = p^{a - k} - p^{a - k - 1} (f or m u l a v a l i d a p er a > k)

φ(p^{a - k}) = p^{a - k} - p^{a - k - 1} (formula~valida~per~a \gt k)

Inoltre, per $i = p^{a}$ i = p^a abbiamo: $M C D (i, p^{a}) = M C D (p^{a}, p^{a}) = p^{a}$ MCD(i, p^a) = MCD(p^a, p^a) = p^a.

Pertanto

g (p^{a}) = k = 0 \sum a - 1 p^{k} φ (p^{a - k}) + p^{a} = k = 0 \sum a - 1 p^{k} (p^{a - k} - p^{a - k - 1}) + p^{a} = k = 0 \sum a - 1 (p^{a} - p^{a - 1}) + p^{a} = a (p^{a} - p^{a - 1}) + p^{a} = (a + 1) p^{a} - a p^{a - 1}

g(p^a) = \sum_{k=0}^{a-1} p^k \varphi\left(p^{a-k}\right) + p^a = \sum_{k=0}^{a-1} p^k \left(p^{a-k} - p^{a-k-1}\right) + p^a \\ = \sum_{k=0}^{a-1} \left(p^a - p^{a-1}\right) + p^a = a\left(p^a - p^{a-1}\right) + p^a = (a+1)p^a - ap^{a-1}

Esempio. Sia $n = 6$ n = 6.

Allora

g (6) = i = 1 \sum 6 g cd (i, 6) = = M C D (1, 6) + M C D (2, 6) + M C D (3, 6) + M C D (4, 6) + M C D (5, 6) + M C D (6, 6) = = 1 + 2 + 3 + 2 + 1 + 6 = 15

g(6) = \sum_{i=1}^{6} \gcd(i,6) = \\ = MCD(1, 6) + MCD(2, 6) + MCD(3, 6) + MCD(4, 6) + MCD(5, 6) + MCD(6, 6) = \\ = 1 + 2 + 3 + 2 + 1 + 6 = 15

Allo stesso tempo

g (6) = g (2) \cdot g (3) = (M C D (1, 2) + M C D (2, 2)) \cdot (M C D (1, 3) + M C D (2, 3) + M C D (3, 3)) = (1 + 2) \cdot (1 + 1 + 3) = 3 \cdot 5 = 15

g(6) = g(2) \cdot g(3) = \\ (MCD(1, 2) + MCD(2, 2)) \cdot (MCD(1, 3) + MCD(2, 3) + MCD(3, 3)) = \\ (1 + 2) \cdot (1 + 1 + 3) = 3 \cdot 5 = 15

Calcoliamo $g (6)$ con la formula $g (n) = n \sum_{d ∣ n} \frac{φ ( d )}{d}$ g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}

g (6) = 6 d ∣ 6 \sum \frac{φ ( d )}{d} = 6 \cdot (\frac{φ ( 1 )}{1} + \frac{φ ( 2 )}{2} + \frac{φ ( 3 )}{3} + \frac{φ ( 6 )}{6}) = 6 φ (1) + 3 φ (2) + 2 φ (3) + φ (6) = 6 + 3 + 4 + 2 = 15

g(6) = 6 \sum_{d \mid 6} \frac{\varphi(d)}{d} = 6 \cdot \left(\frac{\varphi(1)}{1}+ \frac{\varphi(2)}{2} + \frac{\varphi(3)}{3} + \frac{\varphi(6)}{6} \right) \\ = 6\varphi(1) + 3\varphi(2) + 2\varphi(3) + \varphi(6) = 6 + 3 + 4 + 2 = 15

Calcoliamo $g (6)$ a partire dalla moltiplicatività della funzione $f (x) = M C D (x, n)$ f(x) = MCD(x, n):

g (6) = g (2) \cdot g (3) = (2 \cdot 2 - 1) \cdot (2 \cdot 3 - 1) = 3 \cdot 5 = 15

g(6) = g(2) \cdot g(3) = (2 \cdot 2 - 1) \cdot (2 \cdot 3 - 1) = 3 \cdot 5 = 15

Esempio. Sia $n = 12$ n = 12.

Allora

g (12) = i = 1 \sum 12 g cd (i, 12) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12 = 40

g(12) = \sum_{i=1}^{12} \gcd(i,12) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12 = 40

Allo stesso tempo

g (12) = g (4) \cdot g (3) = (M C D (1, 4) + M C D (2, 4) + M C D (3, 4) + M C D (4, 4)) \cdot (M C D (1, 3) + M C D (2, 3) + M C D (3, 3)) = (1 + 2 + 1 + 4) \cdot (1 + 1 + 3) = 8 \cdot 5 = 40

g(12) = g(4) \cdot g(3) = \\ (MCD(1, 4) + MCD(2, 4) + MCD(3, 4) + MCD(4, 4)) \cdot \\ (MCD(1, 3) + MCD(2, 3) + MCD(3, 3)) = \\ (1 + 2 + 1 + 4) \cdot (1 + 1 + 3) = 8 \cdot 5 = 40

Calcoliamo $g (12)$ con la formula $g (n) = n \sum_{d ∣ n} \frac{φ ( d )}{d}$ g(n) = n \sum_{d \mid n} \frac{\varphi(d)}{d}:

g (12) = 12 d ∣ 12 \sum \frac{φ ( d )}{d} = 12 \cdot (\frac{φ ( 1 )}{1} + \frac{φ ( 2 )}{2} + \frac{φ ( 3 )}{3} + \frac{φ ( 4 )}{4} + \frac{φ ( 6 )}{6} + \frac{φ ( 12 )}{12}) = 12 φ (1) + 6 φ (2) + 4 φ (3) + 3 φ (4) + 2 φ (6) + φ (12) = 12 + 6 + 8 + 6 + 4 + 4 = 40

g(12) = 12 \sum_{d \mid 12} \frac{\varphi(d)}{d} = 12 \cdot \left( \frac{\varphi(1)}{1} + \frac{\varphi(2)}{2} + \frac{\varphi(3)}{3} + \frac{\varphi(4)}{4} + \frac{\varphi(6)}{6} + \frac{\varphi(12)}{12} \right) \\ = 12\varphi(1) + 6\varphi(2) + 4\varphi(3) + 3\varphi(4) + 2\varphi(6) + \varphi(12) \\ = 12 + 6 + 8 + 6 + 4 + 4 = 40

I divisori del numero $12$ sono: $1, 2, 3, 4, 6, 12$ 1, 2, 3, 4, 6, 12. Il numero di valori $i$ tali che $M C D (i, 12) = d$ MCD(i, 12) = d è pari a $ϕ (12/ d)$ . Ad esempio $M C D (i, 12) = 3$ MCD(i, 12) = 3 si verifica per $ϕ (12/3) = ϕ (4) = 2$ ϕ(12/3) = ϕ(4) = 2 valori distinti di $i$ , ossia per $i = 3, 9$ i = 3, 9.

Calcoliamo $g (12)$ a partire dalla moltiplicatività della funzione $f (x) = M C D (x, n)$ f(x) = MCD(x, n):

g (12) = g (2^{2}) \cdot g (3) = (3 \cdot 2^{2} - 2 \cdot 2) \cdot (2 \cdot 3 - 1) = 8 \cdot 5 = 40

g(12) = g(2^2) \cdot g(3) = (3 \cdot 2^2 - 2 \cdot 2) \cdot (2 \cdot 3 - 1) = 8 \cdot 5 = 40

Implementazione dell'algoritmo

La funzione euler calcola la funzione di Eulero.

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;
}

C++

Parte principale del programma. Leggiamo il valore di $n$ . Calcoliamo il valore di $g (n)$ con la formula $\sum_{e ∣ n} e φ (\frac{n}{e})$ \sum_{e \mid n} e \varphi\left(\frac{n}{e}\right). Cerchiamo tutti i divisori del numero $n$ tra i numeri da $1$ a $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor.

Se $i$ è un divisore di $n$ , allora anche il numero $n / i$ è un divisore di $n$ . Pertanto, nel trovare ogni divisore $i \leq ⌊ n ⌋$ i \le \lfloor \sqrt{n} \rfloor, al risultato $r es$ bisogna aggiungere $i ϕ (\frac{n}{i}) + \frac{n}{i} ϕ (i)$ i \phi(\frac{n}{i}) + \frac{n}{i} \phi(i), che tiene conto di entrambi i divisori $i$ e $n / i$ .

Se $n$ è un quadrato perfetto e $i = s q = ⌊ n ⌋$ i = sq = \left\lfloor \sqrt{n} \right\rfloor, allora i divisori $i$ e $n / i$ coincidono. In questo caso $i ϕ (\frac{n}{i}) = \frac{n}{i} ϕ (i)$ iϕ(\frac{n}{i}) = \frac{n}{i} ϕ(i) e nella somma $r es$ verrebbero aggiunti due addendi identici. Per questo motivo, uno di essi viene sottratto da $r es$ già in fase di inizializzazione di questa variabile.

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);
}

C++

Implementazione dell'algoritmo – utilizzando la moltiplicatività

Scomponiamo il numero $n$ in fattori primi:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} ... p_{k}^{a_{k}}

n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}

Abbiamo dimostrato che la funzione $g (n) = \sum_{i = 1}^{n} g cd (i, n)$ g(n) = \sum_{i=1}^{n} \gcd(i,n) è moltiplicativa. Di conseguenza

g (n) = g (p_{1}^{a_{1}}) \cdot g (p_{2}^{a_{2}}) \cdot \dots \cdot g (p_{k}^{a_{k}})

g(n) = g(p_1^{a_1}) \cdot g(p_2^{a_2}) \cdot \ldots \cdot g(p_k^{a_k})

E per la potenza di un numero primo abbiamo dimostrato la formula:

g (p^{a}) = (a + 1) p^{a} - a p^{a - 1}

g(p^a) = (a + 1)p^a - ap^{a-1}

Sono proprio queste due formule ad essere utilizzate direttamente nel programma.

Elaboriamo più casi di test. Leggiamo il valore di $n$ .

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

Nella variabile $r es$ calcoleremo il valore di $g (n)$ .

  res = 1;

Scomponiamo in fattori primi il numero $n$ . Esaminiamo i divisori.

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

Se il numero $i$ è primo, isoliamo il fattore $p = i^{a}$ p = i^a.

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

C++

Moltiplichiamo il risultato $r es$ per

g (p) = g (i^{a}) = (a + 1) \cdot i^{a} - a \cdot i^{a - 1} = (a + 1) \cdot p - a \cdot p / i

g(p) = g(i^a) = (a + 1) \cdot i^a - a \cdot i^{a - 1} = (a + 1) \cdot p - a \cdot p / i

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

Se $n > 1$ n > 1, allora $n$ è l'ultimo fattore primo.

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

Stampiamo la risposta.

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

Implementazione in Java

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();
  }
}

Java