ƏBOB-ların cəmi (Həll təhlili)

Hər bir test üçün giriş ədədləri qrupunu $mas$ massivinə yerləşdiririk. Daha sonra hər bir (i, j)~(0 \le i < j < m) cütü üçün ƏBOB(mas[i], mas[j]) hesablayırıq və onu ümumi cəmlə əlavə edirik.

Nümunə

Üçüncü nümunə üçün cavab bərabərdir

Alqoritmin həyata keçirilməsi

Giriş ədədlərini $m$ massivində saxlayırıq.

#define MAX 110
int m[MAX];

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq bölənini qaytarır.

int gcd(int a, int b)
{
  return (!b) ? a : gcd(b, a % b);
}

Proqramın əsas hissəsi. Testlərin sayını $tests$ oxuyuruq.

scanf("%d", &tests);
while (tests--)
{

Hər bir test üçün giriş məlumatlarını oxuyuruq.

  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

Axtarılan cəmi $res$ dəyişənində hesablayırıq.

  res = 0;

Bütün mümkün $(i,j)$ indeks cütlərini (0 \le i < j < n) sırayla keçirik, hər bir cüt üçün ƏBOB(m[i], m[j]) hesablayırıq və bu qiyməti $res$-ə əlavə edirik.

  for (i = 0; i < n; i++)
  for (j = i + 1; j < n; j++)
    res += gcd(m[i], m[j]);

Cavabı çap edirik.

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

Python icrası

Testlərin sayını $tests$ oxuyuruq.

tests = int(input())

Hər bir test üçün giriş məlumatlarını oxuyuruq.

for _ in range(tests):
  n, *lst = list(map(int, input().split()))

Axtarılan cəmi $res$ dəyişənində hesablayırıq.

  res = 0

Bütün mümkün $(i,j)$ indeks cütlərini (0 \le i < j < n) sırayla keçirik, hər bir cüt üçün ƏBOB(m[i], m[j]) hesablayırıq və bu qiyməti $res$-ə əlavə edirik.

  for i in range(n):
    for j in range(i + 1, n):
      res += math.gcd(lst[i], lst[j])

Cavabı çap edirik.

  print(res)