Тема 25. Программирование - Обработка целочисленной информации

25.05 Прочие прототипы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела программирование - обработка целочисленной информации

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#11534

Крабьи числа - это числа, единственные простые множители которых равны $2$ , $3$ или $5$ . Последовательность $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $8$ , $9$ , $10$ , $12$ , $15$ ,… показывает первые $11$ крабих чисел. По соглашению $1$ включен. Найдите $100$ -ое крабье число.

Показать ответ и решение

a=[]
for i in range(100):
    for j in range(100):
        for k in range(100):
            a.append((2**i)*(3**j)*(5**k))
a.sort()
print(a[99])

Ответ: 1536

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#27883

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

$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

Курсы

Всё необходимое для достижения цели

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел