Задача к ЕГЭ по информатике на тему «Программирование - Обработка целочисленной информации» №4

Задача к ЕГЭ по информатике на тему «Программирование — Обработка целочисленной информации» №4

Просмотров 12 Комментарии 0

Напишите программу, которая вычислит среднее арифметическое значений

$aφ(1013)%1013$ , где a это числа, не превышающие 1013 и взаимно простые с ним.

По теореме Эйлера $aφ(n) ≡ 1(mod n)$ , так что все значения равны 1, и, следовательно, их среднее – тоже. (Кстати, из того, что $φ(p) = p− 1$ для простых p следует Малая теорема Ферма $ap−1 ≡ 1(mod p)$ , которая применима и в этой задаче, так как 1013 простое).

print(1)

$\text{[math]}$

Ладно-ладно, снова шучу. Последний раз, обещаю.

def gcd(a, b):

    if a == b:

        return a

    if a != 0 and b != 0:

        return gcd(a % b, b % a)

    else:

        return a + b

def phi(n):

    fi = 0

    for i in range(1, n + 1):

        if gcd(n, i) == 1:

            fi += 1

    return fi

n = 1013

sum = 0

count = 0

for a in range(1, n + 1):

    if gcd(n, a) == 1:

        sum += (a ** phi(n)) % n

        count += 1

print(sum // count)

$\text{[math]}$

Ответ: 1