Estremo di Eulero#4107

Estremo di Eulero (Editoriale)

Riscriviamo la somma indicata $H$ nel modo seguente:

φ (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)

φ(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)

Raggruppiamo gli addendi nella somma $H$ per fattore comune:

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

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

In tutti gli addendi è presente lo stesso fattore. Mettiamolo in evidenza:

H = (φ (1) + φ (2) + \dots φ (n))^{2}

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

Implementiamo un crivello che calcoli tutti i valori della funzione di Eulero da $1$ a $1 0^{4}$ 10^4 e li salvi nell'array $f i$ . Successivamente costruiamo l'array delle somme parziali $s u m$ , dove

s u m [i] = φ (1) + φ (2) + ... + φ (i)

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

Dopodiché, per ogni valore di input $n$ , stampiamo il prodotto

s u m [n] \cdot s u m [n]

sum[n] \cdot sum[n]

Esempio

Consideriamo lo stato dell'array dei valori della funzione di Eulero $f i$ e dell'array delle somme parziali $s u m$ :

Per $n = 10$ n = 10 la risposta è pari a

(φ (1) + φ (2) + \dots φ (10))^{2} = s u m [10]^{2} = 3 2^{2} = 1024

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

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro $f i$ e $s u m$ , dove

$f i [i] = φ (i)$ fi[i] = φ(i);
$s u m [i] = φ (1) + φ (2) + ... φ (i)$ sum[i] = φ(1) + φ(2) + ... φ(i)

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

La funzione FillEuler riempie l'array $f i$ con i valori della funzione di Eulero:

f i [i] = φ (i) p er t u tt i 1 \leq i 0 ˘ 03 c M A X

fi[i] = φ(i)~per~tutti~1 ≤ i \u003c MAX

void FillEuler(void)
{
  int i, j;
  for (i = 0; i \u003c MAX; i++) fi[i] = i;
  for (i = 2; i \u003c MAX; i++)
    if (fi[i] == i)
      for (j = i; j \u003c MAX; j += i)
        fi[j] -= fi[j] / i;

C++

Calcoliamo le somme parziali $s u m [i]$ . Inizializziamo i primi elementi dell'array.

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

Poi calcoliamo in sequenza le rimanenti somme parziali.

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

Parte principale del programma. Riempiamo gli array $f i$ e $s u m$ .

FillEuler();

Elaboriamo $t es t s$ test.

scanf("%d",\u0026tests);
while(tests--)
{
  scanf("%d",\u0026n);

Per ogni valore di input $n$ calcoliamo e stampiamo la risposta

s u m [n] \cdot s u m [n] = (φ (1) + φ (2) + \dots φ (n))^{2}

sum[n] \cdot sum[n] = (φ(1) + φ(2) + … φ(n))^2

  res = sum[n] * sum[n];
  printf("%lld\n",res);
}