Задание №25 ЕГЭ Информатика с ответом и решением
Ответ: 53831655 26505 333126651 164021 512313657 252247 647931651 319021 831966654 409634
Условие
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Найдите все натуральные числа, не превосходящие 109, для которых выполнены все условия:
— соответствуют маске *31*65?;
— делятся на 31 и 2031 без остатка;
— количество делителей числа является результатом любой степени двойки.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, справа от каждого числа их частное от деления на 2031.
Подсказки — как подойти к решению
- Кроме маски и делимости здесь есть третье условие — количество делителей числа. Считай делители парами до квадратного корня и не забудь, что каждому маленькому делителю отвечает большой.
- Во втором столбце — частное от деления на тот делитель, который указан в условии для частного; не путай его с другим делителем из условия. Пары выписывай по возрастанию чисел.
Решение
Приведём решение на языке Python.
from fnmatch import *
sd = []
for i in range (1,20):
sd.append(2**i)
for x in range(0, 10**9, 31*2031):
if fnmatch(str(x), '*31*65?'):
delitel = []
for i in range(1, round (x**0.5) + 1):
if x%i==0:
delitel.append(i)
delitel.append(x // i)
if len(delitel) in sd:
print(x, x // 2031)
В результате работы программа должна вывести следующее:
53831655 26505
333126651 164021
512313657 252247
647931651 319021
831966654 409634
Приведём решение Сергея Калугина на языке Python.
from fnmatch import *
for i in range(0,10**9+1,2031):
if fnmatch(str(i),'*31*65?') and i%31==0:
d=[]
for j in range(1,int(i**0.5)+1):
if i%j==0:
d.append(j)
if j!=(i//j):
d.append(i//j)
for x in range(100):
if len(d)==2**x:
print(i,i//2031)
break
Приведём решение Артёма Гридина на языке Python.
import math
for i in range(0, 10**9, math.lcm(31, 2031)): #Для python 3.8 и раньше: for i in range(0, 10**9, abs(31*2031)//math.gcd(31, 2031), 2):
s = str(i)
if s[::-1][1:3] == '56' and '13' in s[::-1][3:]:
divCount = 1
for d in range(2, math.floor(math.sqrt(i))+1):
if i%d == 0:
divCount+=1
if divCount in [2**t for t in range(1, math.ceil(9*math.log2(10)))]: #10**9 >= 2**x <=> x <= 9*log₂10
print(i, i//2031)
Приведём решение Юрия Красильникова на языке Python.
import fnmatch,math
def deliteli(n):
d=set()
k=1
while k**2<=n:
if n%k==0: d|={k,n//k}
k+=1
return sorted(d)
twopower=[2**n for n in range(100)]
for n in range(0,10**9,31*2031//math.gcd(31,2031)):# шаг цикла - наименьшее общее кратное
if fnmatch.fnmatch(str(n),'*31*65?') and len(deliteli(n)) in twopower:
print(n,n//2031)
Ответ: 53831655 26505 333126651 164021 512313657 252247 647931651 319021 831966654 409634.
Типичные ошибки
- Пары выписаны в порядке нахождения, а не по возрастанию чисел. Отсортируй найденные числа перед тем, как формировать второй столбец.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №25 по информатике