Eyler ekstremumu#4107

Eyler ekstremumu (Həll təhlili)

Göstərilən $H$ cəmini aşağıdakı kimi yenidən yazaq:

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

$H$ cəmindəki hədləri ümumi vuruğa görə qruplaşdıraq:

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

Bütün hədlərdə eyni vuruq iştirak edir. Onu mötərizədən kənara çıxaraq:

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

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

Əvvəlcə $1$ -dən $1 0^{4}$ 10^4-ə qədər olan bütün dəyərlər üçün Eyler funksiyasını hesablayan ələk qurub nəticələri $f i$ massivində saxlayaq. Sonra qismi cəmlər massivi $s u m$ qurulsun, burada

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

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

Bundan sonra hər giriş dəyəri $n$ üçün

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

sum[n] \cdot sum[n]

hasilini çap edək.

Misal

Eyler funksiyasının dəyərlər massivi $f i$ və qismi cəmlər massivi $s u m$ -ın vəziyyətinə baxaq:

$n = 10$ n = 10 üçün cavab bərabərdir:

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

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

Alqoritmin realizasiyası

İşçi $f i$ və $s u m$ massivlərini elan edək, burada

$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];

FillEuler funksiyası $f i$ massivini Eyler funksiyasının dəyərləri ilə doldurur:

f i [i] = φ (i) b u ¨ t u ¨ n 1 \leq i 0 ˘ 03 c M A X u ¨ c \c u ¨ n

fi[i] = φ(i)~bütün~1 ≤ i \u003c MAX~üçün

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++

$s u m [i]$ qismi cəmlərini hesablayırıq. Massivin ilk elementlərini ilkinləşdiririk.

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

Sonra qalan qismi cəmləri ardıcıl olaraq hesablayırıq.

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

Proqramın əsas hissəsi. $f i$ və $s u m$ massivlərini doldururuq.

FillEuler();

$t es t s$ testini emal edirik.

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

Hər giriş dəyəri $n$ üçün cavabı hesablayıb çap edirik

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