ЕГЭ по информатике · задание 25

Делители и маски: ответ таблицей

Нужно написать программу перебора чисел: найти делители с условием или числа, подходящие под маску. Ответ — таблица из нескольких строк по два числа.

Делители

Перебор d от 2 до √n: делители идут парами d и n / d.
Наименьший делитель больше 1 — всегда простое число.
Нечётное количество делителей — только у точных квадратов.

Маски

fnmatch(str(x), '12?4*5') — проверка числа по маске.
Перебирать нужно кратные: range(D, 10 ** 10 + 1, D).

Как вводить ответ

Каждая строка таблицы — два числа через пробел, например 800004 400004.
Количество строк в ответе может быть меньше, чем строк в таблице бланка.

Разобранные варианты

Вариант 1

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 732 400 в порядке возрастания и ищет среди них такие для которых M оканчивается на 1. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.

Разбор

Идея. Наименьший делитель, кроме 1, — это наименьший простой делитель d; наибольший делитель, кроме самого числа, — n / d. Ищем d перебором от 2 до √n: если делителей нет, число простое и M = 0.

Ответ (число — M): 732418 — 366211; 732438 — 366221; 732458 — 366231; 732478 — 366241; 732498 — 366251.

Ответ: 732418 366211; 732438 366221; 732458 366231; 732478 366241; 732498 366251

Решение на Python.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d + n // d
        d += 1
    return 0

n = 732400
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m != 0 and m % 10 == 1:
        print(n, m)
        found += 1

Вариант 2

маска числа · строк: 4

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 567?0?1*2, делящиеся на 5898 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 5898.

Разбор

Идея. Перебирать все числа до 10¹⁰ слишком долго а кратных 5898 — около 1 695 489 — это уже быстро. Для каждого кратного проверяем строку числа на соответствие маске: модуль fnmatch понимает «?» и «*» именно так как в условии (для чисел из цифр).

Ответ (число — частное): 5672041722 — 961689; 5672071212 — 961694; 5676081852 — 962374; 5679001362 — 962869.

Ответ: 5672041722 961689; 5672071212 961694; 5676081852 962374; 5679001362 962869

Решение на Python.

from fnmatch import fnmatch

D = 5898
for x in range(D, 10 ** 10 + 1, D):
    if fnmatch(str(x), '567?0?1*2'):
        print(x, x // D)

Вариант 3

ровно 3 нечётных делителей · строк: 6

Найдите все натуральные числа принадлежащие отрезку [659 256; 682 881] у которых ровно 3 различных нечётных делителя. В ответе перечислите найденные числа в порядке возрастания справа от каждого числа укажите наибольший из его нечётных делителей.

Разбор

Идея. Делители ищем парами: если d делит n, то делит и n / d, поэтому достаточно перебрать d до √n.

Ответ (число — наибольший делитель): 665858 — 332929; 669124 — 167281; 674041 — 674041; 677329 — 677329; 678976 — 10609; 682112 — 5329.

Ответ: 665858 332929; 669124 167281; 674041 674041; 677329 677329; 678976 10609; 682112 5329

Решение на Python.

def divisors(n):
    s = set()
    d = 1
    while d * d <= n:
        if n % d == 0:
            s.add(d)
            s.add(n // d)
        d += 1
    return s

for n in range(659256, 682882):
    ds = [d for d in divisors(n) if d % 2 == 1]
    if len(ds) == 3:
        print(n, max(ds))

Вариант 4

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 887 500 в порядке возрастания и ищет среди них такие для которых M оканчивается на 0. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.

Разбор

Ответ (число — M): 887501 — 38610; 887511 — 295840; 887516 — 443760; 887521 — 5810; 887525 — 177510.

Ответ: 887501 38610; 887511 295840; 887516 443760; 887521 5810; 887525 177510

Решение на Python.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d + n // d
        d += 1
    return 0

n = 887500
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m != 0 and m % 10 == 0:
        print(n, m)
        found += 1

Вариант 5

маска числа · строк: 2

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 8??9*3310, делящиеся на 6343 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 6343.

Разбор

Идея. Перебирать все числа до 10¹⁰ слишком долго а кратных 6343 — около 1 576 541 — это уже быстро. Для каждого кратного проверяем строку числа на соответствие маске: модуль fnmatch понимает «?» и «*» именно так как в условии (для чисел из цифр).

Ответ (число — частное): 8659273310 — 1365170; 8849563310 — 1395170.

Ответ: 8659273310 1365170; 8849563310 1395170

Решение на Python.

from fnmatch import fnmatch

D = 6343
for x in range(D, 10 ** 10 + 1, D):
    if fnmatch(str(x), '8??9*3310'):
        print(x, x // D)

Вариант 6

ровно 3 чётных делителей · строк: 5

Найдите все натуральные числа принадлежащие отрезку [143 462; 163 130] у которых ровно 3 различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания справа от каждого числа укажите наибольший из его чётных делителей.

Разбор

Идея. Делители ищем парами: если d делит n, то делит и n / d, поэтому достаточно перебрать d до √n.

Ответ (число — наибольший делитель): 144722 — 144722; 146882 — 146882; 153458 — 153458; 157922 — 157922; 160178 — 160178.

Ответ: 144722 144722; 146882 146882; 153458 153458; 157922 157922; 160178 160178

Решение на Python.

def divisors(n):
    s = set()
    d = 1
    while d * d <= n:
        if n % d == 0:
            s.add(d)
            s.add(n // d)
        d += 1
    return s

for n in range(143462, 163131):
    ds = [d for d in divisors(n) if d % 2 == 0]
    if len(ds) == 3:
        print(n, max(ds))

Вариант 7

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 530 900 в порядке возрастания и ищет среди них такие для которых M при делении на 7 даёт остаток 3. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.

Разбор

Ответ (число — M): 530901 — 176970; 530903 — 18336; 530905 — 106186; 530910 — 265457; 530924 — 265464.

Ответ: 530901 176970; 530903 18336; 530905 106186; 530910 265457; 530924 265464

Решение на Python.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d + n // d
        d += 1
    return 0

n = 530900
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m != 0 and m % 7 == 3:
        print(n, m)
        found += 1

Вариант 8

маска числа · строк: 2

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1?861*3?6, делящиеся на 7181 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 7181.

Разбор

Идея. Перебирать все числа до 10¹⁰ слишком долго а кратных 7181 — около 1 392 563 — это уже быстро. Для каждого кратного проверяем строку числа на соответствие маске: модуль fnmatch понимает «?» и «*» именно так как в условии (для чисел из цифр).

Ответ (число — частное): 1086169336 — 151256; 1586182366 — 220886.

Ответ: 1086169336 151256; 1586182366 220886

Решение на Python.

from fnmatch import fnmatch

D = 7181
for x in range(D, 10 ** 10 + 1, D):
    if fnmatch(str(x), '1?861*3?6'):
        print(x, x // D)

Вариант 9

ровно 3 нечётных делителей · строк: 6

Найдите все натуральные числа принадлежащие отрезку [401 083; 411 947] у которых ровно 3 различных нечётных делителя. В ответе перечислите найденные числа в порядке возрастания справа от каждого числа укажите наибольший из его нечётных делителей.

Разбор

Идея. Делители ищем парами: если d делит n, то делит и n / d, поэтому достаточно перебрать d до √n.

Ответ (число — наибольший делитель): 401408 — 49; 401956 — 100489; 403202 — 201601; 408608 — 12769; 409600 — 25; 410881 — 410881.

Ответ: 401408 49; 401956 100489; 403202 201601; 408608 12769; 409600 25; 410881 410881

Решение на Python.

def divisors(n):
    s = set()
    d = 1
    while d * d <= n:
        if n % d == 0:
            s.add(d)
            s.add(n // d)
        d += 1
    return s

for n in range(401083, 411948):
    ds = [d for d in divisors(n) if d % 2 == 1]
    if len(ds) == 3:
        print(n, max(ds))

Вариант 10

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 871 800 в порядке возрастания и ищет среди них такие для которых M при делении на 17 даёт остаток 15. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.

Разбор

Ответ (число — M): 871820 — 435912; 871854 — 435929; 871879 — 51304; 871881 — 290630; 871888 — 435946.

Ответ: 871820 435912; 871854 435929; 871879 51304; 871881 290630; 871888 435946

Решение на Python.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d + n // d
        d += 1
    return 0

n = 871800
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m != 0 and m % 17 == 15:
        print(n, m)
        found += 1

Для самостоятельного решения

Вариант 11

маска числа · строк: 2

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 153*6?67?, делящиеся на 8573 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 8573.

Вариант 12

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 1 254 600 в порядке возрастания и ищет среди них такие для которых M при делении на 7 даёт остаток 1. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.

Вариант 13

ровно 3 нечётных делителей · строк: 3

Найдите все натуральные числа принадлежащие отрезку [846 104; 853 951] у которых ровно 3 различных нечётных делителя. В ответе перечислите найденные числа в порядке возрастания справа от каждого числа укажите наибольший из его нечётных делителей.

Вариант 14

маска числа · строк: 4

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 6?5*788?9, делящиеся на 5081 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им результаты деления этих чисел на 5081.

Вариант 15

наименьший и наибольший делители · строк: 5

Пусть M — сумма минимального и максимального натуральных делителей целого числа не считая единицы и самого числа. Если таких делителей у числа нет то значение M признаётся равным нулю. Напишите программу которая перебирает целые числа бо́льшие 691 500 в порядке возрастания и ищет среди них такие для которых M при делении на 13 даёт остаток 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания а во втором столбце — соответствующие им значения M. Например для числа 20 M = 2 + 10 = 12.