РЕШУ ЕГЭ — информатика

Задания

Пусть M  — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце  — соответствующие им значения M.

Например, для числа 20 М  =  2 + 10  =  12.

Количество строк в таблице для ответа избыточно.

Ответ:

ИЛИ

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

—  символ «?» означает ровно одну произвольную цифру;

—  символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце  — соответствующие им результаты деления этих чисел на 1917.

Количество строк в таблице для ответа избыточно.

Ответ:

Решение. Приведём решение на языке Python.

def deliteli(n):

deliteli = []

for i in range(2, int(n**0.5)+1):

if n % i == 0:

deliteli.append(i)

deliteli.append(n//i)

return deliteli

count = 0

for j in range(800_000, 10**6):

d = deliteli(j)

if len(d) != 0:

M = max(d) + min(d)

if M % 10 == 4:

print(j, M)

count += 1

if count == 5:

break

Ответ:

800004 400004

800009 114294

800013 266674

800024 400014

800033 61554

Приведём решение Александра Козлова на языке Python.

def get_M(n):

mi = ma = None

for i in range(2, int(n**0.5) + 1):

if n % i == 0:

if mi is None: mi = i

if ma is None or (n // i) > ma: ma = n // i

return 0 if mi is None else mi + ma

results = []

for n in range(800_001, 1_000_000):

M = get_M(n)

if M % 10 == 4:

results.append((n, M))

if len(results) == 5: break

for num, M in results:

print(f"{num}\t{M}")

ИЛИ

Будем последовательно рассматривать каждое целое число, кратное 1917, затем каждое число проверять на соответствие маске.

Приведём решение на языке Python.

from fnmatch import *

for x in range(0, 10**10, 1917):

# Перебираем все числа от 0 с шагом 1917, будут получены числа кратные 1917

if fnmatch(str(x), '3?12?14*5'):

# Проверяем полученное число соответствию заданию

print(x, x//1917)

В результате работы программа должна вывести следующее:

351261495 183235

3212614035 1675855

3412614645 1780185

3712414275 1936575

3912414885 2040905

Приведём решение Юрия Красильникова на языке Python.

from itertools import product

d='0123456789'

twod=[''.join(x) for dl in range(3) for x in product(d,repeat=dl)]

a=sorted([int(f'3{x}12{y}14{z}5') for x in d for y in d for z in twod])

for y in [x for x in a if x%1917==0]: print(y,y//1917)

№ п/п	№ задания	Ответ
1	81809	800004 400004 800009 114294 800013 266674 800024 400014 800033 61554\|351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905

Ключ