Programowanie - zadanie

Question

Witam, potrzebuje pomocy z poniższym zadaniem. Szczerze mówiąc nie wiem jak się do tego zabrać. Jeśli ktoś mógłby mnie naprowadzić albo pokazał jak to zrobić to byłbym wdzięczny. Piszę programy w c++.

Answer 1

Możesz wyznaczyć ilość par liczb względnie pierwszych za pomocą poniższej pętli

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n, j++) {
        if (NWD(a[i], a[j]) == 1) {
            licznik++;
        }
    }
}

W zamyśle chodzi o to, że wyznaczasz NWD dla pierwszej liczby ciągu i drugiej, następnie dla pierwszej i trzeciej, aż dojdziesz do pierwszej i ostatniej. Następnie obliczasz NWD dla liczby drugiej i trzeciej... drugiej i ostatniej itd., kiedy nie dojdziesz do liczby przedostatniej i ostatniej. Dzięki temu sprawdzisz wszystkie pary w ciągu, a to umożliwi obliczenie ilości par liczb względnie pierwszych.