Статья Автор: Прохоров Михаил

Делители и необычные условия задания №25

fipi-9C9EF1 (4 из fipi по Дмитрию Алексеевичу)

Напишите программу, которая перебирает целые числа, большие 500 000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 8 и не равный ни самому числу, ни числу 8. Вывести первые пять найденных чисел и для каждого наименьший делитель, оканчивающийся на цифру 8, не равный ни самому числу, ни числу 8.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем через один пробел – значение наименьшего делителя, оканчивающегося на цифру 8, не равного ни самому числу, ни числу 8.
Строки выводятся в порядке возрастания найденных чисел.

def oper(x):
  d = 18
  while d < x:
    if x % d == 0:
      return d
    d += 10
  return False
n = 500000
c = 0
while True:
  op = oper(n)
  if op:
    print(n, op)
    c += 1
  n += 1
  if c == 5:
    break

fipi-D4D5BB (9 из fipi по Дмитрию Алексеевичу)

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.
Напишите программу, которая перебирает целые числа, большие 900 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Программа должна найти и вывести первые пять таких чисел и соответствующие им значения M.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем через один пробел –
значение М.
Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 20 М = 2 + 10 = 12.

def oper1(x):#вариант выполняется быстрее
  if x % 2 == 0:
    return x // 2 + 2
  d = 3
  while d * d <= x:
    if x % d == 0:
      return x // d + d
    d += 2
  return 0
def oper2(x):#вариант пишется быстрее
  d = 2
  while d * d <= x:
    if x % d == 0:
      return x // d + d
    d += 1
  return 0
n = 900000
c = 0
while True:
  op = oper1(n)
  if op % 10 == 8:
    print(n, op)
    c += 1
  if c == 5:
    break
  n += 1

Если вы не знаете шаблон по обычному условию маски, то этот блок для вас.

9. _St-24_03-kege-25(a) (9 из "По следам статграда..." по Дмитрию Алексеевичу)

Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «».
Символ «?» означает ровно одну произвольную цифру,
символ «» означает произвольную (в том числе пустую) последовательность цифр.
Например, маске 1234?5 соответствуют числа 123405 и 12376415.
Найдите все натуральные числа, не превышающие 10⁹, которые
соответствуют маске 2416?9 и при этом без остатка делятся на 9517.
В ответе запишите все найденные числа в порядке возрастания.*
Каждое число вводите в новой строке.

#первый способ: нормальный
from fnmatch import *
for i in range(0, 10 ** 9, 9517):
  if fnmatch(str(i), '2*41*6?9'):
    print(i)
    
print()
#второй способ: для тех, кто любит пожестче
for i in range(0, 10 ** 9, 9517):
  s = str(i)
  if s[0] == '2' and '41' in s[1:6] and s[-3] == '6' and s[-1] == '9':
    print(i)

_St-24_10-kege-25(a) (11 из "По следам статграда..." по Дмитрию Алексеевичу)

Пусть M (N) – сумма 2 наибольших различных натуральных делителей натурального числа N, не считая самого числа и единицы.
Если у числа N меньше 2 таких делителей, то M (N) считается равным 0.

Найдите все такие числа N, что 110 250 000 ≤ N ≤ 110 300 000,
а десятичная запись числа M (N) заканчивается на 1002.

В ответе запишите все найденные числа в порядке возрастания.
Каждое число вводите в новой строке.

def oper(x):
    d = 2
    d1 = -1
    while d * d < x:
        if x % d == 0:
            if d1 == -1:
                d1 = x // d
            else:
                return d1 + x // d
        d += 1
    if d1 != -1:
        return d1 + x // d1
    return 0

for n in range(110_250_000, 110_300_000 + 1):
    if oper(n) % 10000 == 1002:
      print(n)

_St-24_12-kege-25(a) (12 из "По следам статграда..." по Дмитрию Алексеевичу)

Маска числа – это последовательность цифр, в которой могут встречаться специальные символы «?» и «*».

Символ «?» означает ровно одну произвольную цифру,
символ «*» означает произвольную (в том числе пустую) последовательность цифр.

Например, маске 123*4?5 соответствуют числа 123405 и 12376415.
Найдите все натуральные числа, принадлежащие интервалу [10⁸; 2·10⁸],
которые соответствуют маске ?*42*81 и имеют ровно три натуральных делителя.

В ответе запишите все найденные числа в порядке возрастания.
Каждое число вводите в новой строке.

from sympy import isprime
from math import sqrt
from fnmatch import *
for i in range(10 ** 4, int(sqrt(2 * 10 ** 8)) + 1):
  if isprime(i):
    if fnmatch(str(i * i), '?*42*81'):
      print(i * i)

№ 20814 Апробация 05.03.25(kompege)
Пусть R - сумма различных натуральных делителей целого числа, не считая единицы и самого числа.
Напишите программу, которая перебирает целые числа, большие 500 000, в порядке возрастания и ищет среди них такие, для которых R оканчивается на цифру 9.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце - соответствующие им значения R.
Например, для числа 20 R = 2 + 4 + 5 + 10 = 21.
Количество строк в таблице для ответа избыточно.

def oper(x):
    d = 2
    s = 0
    while d * d < x:
        if x % d == 0:
            s += d + x // d
        d += 1
    return s + d if x == d * d else s
n = 500000
c = 0
while True:
    op = oper(n)
    if op % 10 == 9:
        print(n, op)
        c += 1
    if c == 5:
        break
    n += 1

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

1) символ «@» означает ровно одну произвольную нечётную цифру;
2) символ «#» означает любую последовательность чётных цифр произвольной длины; в том числе «#» может задавать и пустую последовательность.
Например, маске 123#4@5 могут соответствовать числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 20@@22#, делящиеся на 10980 без остатка.
В ответе запишите в первом столбце таблицы первые 5 найденных чисел в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 10980.
Количество строк в таблице для ответа избыточно.

#1 способ
c = 0
for i in range(20_11_22 // 10980 * 10980, 10 ** 10, 10980):
  s = str(i)
  if s[:2] == '20' and s[2] in '13579' and s[3] in '13579' and s[4:6] == '22' and all(j in '02468' for j in s[6:]):
    print(i, i // 10980)
    c += 1
  if c == 5:
    break
print('---')
#2 способ
from re import *
c = 0
for i in range(20_11_22 // 10980 * 10980, 10 ** 10, 10980):
  if match(r'20[13579][13579]22[02468]*$', str(i)):
    print(i, i // 10980)
    c += 1
  if c == 5: break
print('---')
#3 способ
from re import *
i = 20_11_22 // 10980 * 10980
for _ in range(5):
  while True:
    i += 10980
    if match(r'20[13579][13579]22[02468]*$', str(i)): break
  print(i, i // 10980)
print('---')
#4 способ(офиц. решение с kompege)
from itertools import *
answers=[]
for c in range(6):
    for d1 in '13579':
        for d0 in '13579':
            for r in product('02468',repeat=c):
                s='20'+d1+d0+'22'+''.join(r)
                if (int(s)%10980==0)and(int(s)<=10**10):
                    answers.append((int(s), int(s)//10980))

answers=sorted(answers)
for i in range(5):
    print(answers[i][0],answers[i][1])

№ 20501 (В. Зарянкин) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:]\

1) символ «?» означает ровно одну произвольную цифру;
2) символ «&» означает последовательность цифр, образующих степень двойки (1, 2, 4, 8, 16, ...).

Например, маске 1?2&3? могут соответствовать числа 1213 и 12483.
Среди натуральных чисел, не превышающих 10¹⁰, найдите числа, соответствующие маске 8902??&, делящиеся на 1432 без остатка.
В ответе запишите в первом столбце таблицы первые 5 найденных чисел в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 1432.
Количество строк в таблице для ответа избыточно.

#1 способ
c = 0
for i in range(8902001 // 1432 * 1432, 10 ** 10, 1432):
  s = str(i)
  if s[0:4] == '8902' and s[6:] in [str(2 ** i) for i in range(0, 14)]:
    print(i, i // 1432)
    c += 1
  if c == 5:
    break
print('---')
#2 способ
from re import *
deg2 = r'(?:' + '|'.join([str(2 ** i) for i in range(0, 14)]) + ')'
c = 0
for i in range(8902001 // 1432 * 1432, 10 ** 10, 1432):
  if match(fr'8902\d\d{deg2}$', str(i)):
    print(i, i // 1432)
    c += 1
  if c == 5:
    break
print('---')
#3 способ(офиц. решение с kompege)
from itertools import *
answers=[]
for q0 in '0123456789':
    for q1 in '0123456789':
        for amp in [str(2**x) for x in range(20)]:
            s='8902'+q0+q1+amp
            if int(s)%1432==0 and int(s)<=10**10:
                answers.append((int(s), int(s)//1432))

answers=sorted(answers)
for i in range(5):
    print(answers[i][0],answers[i][1])
#чтобы получить ответ, нужно подождать

№ 19779 Найдите 5 чисел больших 55 000 000, таких, что среди их простых делителей есть число, оканчивающееся на 777, при не равное самому числу.
В качестве ответа приведите 4 наименьших числа, соответствующих условию.
Формат вывода: для каждого из 4 таких найденных чисел в отдельной строке сначала выводится само число, затем минимальный простой делитель, оканчивающийся на 777, не равный самому числу.
Количество строк для записи ответа избыточно.

#решение из kompege
def div(x):
    d = set()
    i = 2
    while i * i <= x:
        if x%i==0:
            d |= {i, x // i}
        i += 1
    return d

k = 0
for x in range(55_000_001,55_010_000):
    d = [i for i in div(x) if len(div(i))==0 and i%1000==777]
    if len(d)>0:
        print(x,d[0])
        k += 1
    if k==4: break

№ 19778 Обозначим через F целую часть среднего арифметического всех простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение F равным нулю. Напишите программу, которая перебирает целые числа, большие 9 500 000, в порядке возрастания и ищет среди них такие, для которых значение F не равно нулю и кратно 813.
Выведите первые 5 найденных числа в порядке возрастания и справа от каждого числа – соответствующее значение F.
Количество строк для записи ответа избыточно.

#мое решение
def oper(x):
  m = []
  d = 2
  while d * d <= x:
    if x % d == 0:
      m.append(d)
      x //= d
    else:
      d += 1
  if x > 1:
    m.append(x)
  return sum(set(m)) // len(set(m)) if m else 0
n = 9_500_000
c = 0
while True:
  op = oper(n)
  if op and op % 813 == 0:
    print(n, op)
    c += 1
  n += 1
  if c == 5:
    break

print('---')
#офиц. решение
def div(x):
    d = set()
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            d.add(i)
            d.add(x//i)
    return sorted(d)

k = 0
for x in range(9_500_001,9_510_000):
    d = [i for i in div(x) if len(div(i))==0]
    F = sum(d)//len(d) if len(d)>0 else 0
    if F!=0 and F%813==0:
        print(x,F)
        k += 1
        if k==5: break

№ 19775 Обозначим через S сумму простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение S равным нулю. Напишите программу, которая перебирает целые числа, большие 32 500 000 в порядке возрастания и ищет среди них такие, для которых значение S не равно нулю и кратно 145.
Программа должна найти первые 7 таких чисел. Для каждого из них в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке возрастания найденных чисел.
Количество строк для записи ответа избыточно.

#мое решение
def oper(x):
  d = 2
  m = []
  while d * d <= x:
    if x % d == 0:
      m += [d]
      x //= d
    else:
      d += 1
  if x > 1:
    m += [x]
  return sum(set(m))
n = 32_500_000
c = 0
while True:
  op = oper(n)
  if op and op % 145 == 0:
    print(n, op)
    c += 1
  n += 1
  if c == 7:
    break
    
print('---')
#офиц. решение
def div(x):
    d = set()
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            d.add(i)
            d.add(x//i)
    return sorted(d)

k = 0
for x in range(32_500_001,32_501_000):
    d = [i for i in div(x) if len(div(i))==0]
    S = sum(d)
    if S!=0 and S%145==0:
        print(x,S)
        k += 1
        if k==7: break

№ 18962 (Д. Бахтиев) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
1. символ «?» означает ровно одну произвольную цифру;
2. символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Напишите программу, которая перебирает целые числа, бо́льшие 500 000, в порядке возрастания и ищет среди них такие, у которых есть хотя бы один делитель, соответствующий маске 2*3?. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – наименьший их делитель, соответствующий заданной маске.
Количество строк в таблице для ответа избыточно

from fnmatch import *
def oper(x):
  d = 2
  while d * d <= x:
    if x % d == 0:
      if fnmatch(str(d), '2*3?'):
        return d
      if fnmatch(str(x//d), '2*3?'):
        return x // d
    d += 1

n = 500_000 + 1
c = 0
while True:
  op = oper(n)
  if op:
    print(n, op)
    c += 1
  n += 1
  if c == 5:
    break

№ 18591 (Д. Бахтиев) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность;
– символ «Н» означает ровно одну нечётную цифру;
– символ «Ч» означает ровно одну чётную цифру.
Например, маске 1Ч3*4?Н соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске Ч9?23?*23НЧ и делящиеся на 1984 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им
результаты деления этих чисел на 1984.
Количество строк в таблице для ответа избыточно.

#1 способ
for i in range(2902302310// 1984 * 1984, 10 ** 10, 1984):
  s = str(i)
  if s[0] in '2468' and s[1] == '9' and s[3:5] == '23' and s[-4:-2] == '23' and s[-2] in '13579' and s[-1] in '02468':
    print(i, i // 1984)#кстати, * в данном случае означает только пустую последовательность
    
print('---')
#2 способ
from re import *
for i in range(2902302310// 1984 * 1984, 10 ** 10, 1984):
  if match(r'[2468]9.23..*23[13579][02468]',str(i)):
    print(i, i // 1984)

print('---')
#3 способ
from fnmatch import *
for i in range(2902302310// 1984 * 1984, 10 ** 10, 1984):
  s = str(i)
  if fnmatch(s, '?9?23?*23??') and s[0] in '2468' and s[-2] in '13579' and s[-1] in '02468':
    print(i, i // 1984)

№ 18298 (Д. Бахтиев) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «#» означает любую последовательность чётных цифр произвольной длины; в том числе «#» может задавать и пустую последовательность.
Например, маске 123#4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1592#6?8 и делящиеся на 1996 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им
результаты деления этих чисел на 1996.
Количество строк в таблице для ответа избыточно.

#1 способ
for i in range(1592608 // 1996 * 1996, 10 ** 10, 1996):
  s = str(i)
  if s[0:4] == '1592' and all(j in '02468' for j in s[4:-3])  and s[-3] == '6' and s[-1] == '8':
    print(i, i // 1996)
    
print('---')
#2 способ
from re import *
for i in range(1592608 // 1996 * 1996, 10 ** 10, 1996):
  if match(r'1592[02468]*6.8$', str(i)):
    print(i, i // 1996)
    
print('---')
#3 способ
from fnmatch import *
for i in range(1592608 // 1996 * 1996, 10 ** 10, 1996):
  s = str(i)
  if fnmatch(s, '1592*6?8') and all(j in '02468' for j in s[4:-3]):
    print(i, i // 1996)
#Далее буду решать только регулярками

№ 18192 (Д. Бахтиев) Напишите программу, которая перебирает целые числа, бо́льшие 1 000 000, в порядке возрастания и ищет среди них те, которые имеют ровно 3 простых делителя. В ответе запишите 5 наименьших таких чисел в порядке возрастания. Справа от каждого такого числа укажите его наибольший простой делитель

def oper(x):
	m = []
    d = 2
    while d * d <= x:
      if x % d == 0:
        m += [d]
        x //= d
      else:
        d += 1
    if x > 1:
      m += [x]
    return max(m) if len(set(m)) == 3 else 0
n = 1_000_000 + 1
c = 0
while True:
  op = oper(n)
  if op:
    print(n, op)
    c += 1
  n += 1
  if c == 5:
    break

№18032 (Л. Шастин) Пусть S – сумма всех делителей целого числа. Например, для числа 12 значение S=1+2+3+4+6+12=28.

Напишите программу, которая перебирает все четырёхзначные натуральные числа, и ищет среди них такие, для которых S оканчивается на 23. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им значения SS
Количество строк в таблице для ответа избыточно.

def oper(x):
  m = set()
  d = 1
  while d * d <= x:
    if x % d == 0:
      m |= {d, x // d}
    d += 1
  return sum(m)
for i in range(1000, 10000):
  if oper(i) % 100 == 23:
    print(i, oper(i))

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

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

Например, маске 12N3*4?5 соответствуют числа 123405, 12253405 и 12300405.
Среди чисел до 10⁸ найдите числа, удовлетворяющие маске 1N03*6*, кратные числу 22768.
В ответе запишите: в первом столбце - сами числа в порядке возрастания, во втором - чему равно число N в этих числах (без незначащих нулей).
Примечание: пустая последовательность не является числом.

from sympy import isprime
from re import *
for i in range(0, 10 ** 8, 22768):
  res = match(r'1(.+)03.*6.*$', str(i))
#странное условие: про пустую в N говорят, а потом пишут, что она не подходит... зачем вообще о ней говорить
  if res:
    N = int(res.group(1))
    if not(isprime(N)):
    	print(i, N)

№ 14442 (Л. Шастин) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*475 соответствуют числа 123475 и 12300475.

Особыми назовем числа, которые соответствуют маске *7?. Найдите все натуральные числа, принадлежащие отрезку [400 000; 500 000] и имеющие хотя бы 18 особых делителей. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им суммы их особых делителей.
Количество строк в таблице для ответа избыточно.

def special18(x):
  d = 1
  m = set()
  while d * d <= x:
    if x % d == 0:
      if d // 10 % 10 == 7:
        m |= {d}
      if (x // d) // 10 % 10 == 7:
        m |= {x // d}
    d += 1
  return sum(m) if len(m) >= 18 else 0

for i in range(400000, 500001):
  sp = special18(i)
  if sp:
    print(i, sp)

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

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

– символ «#» означает последовательность из ровно трёх нечётных цифр.

Например, маске 123#4?5 соответствуют числа 123333405 и 123171405. Среди натуральных чисел, не превышающих 10¹⁰ , найдите все числа, соответствующие маске 71#39?28, делящиеся на 2024 без остатка. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2024.

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

from re import *

for i in range(7111139028// 2024 * 2024, 10 ** 10, 2024):
  if match(r'71[13579]{3}39.28$', str(i)):
    print(i, i // 2024)

№ 14441 (Л. Шастин) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*475 соответствуют числа 123475 и 12300475.
Среди натуральных чисел, не превышающих 10⁹, найдите все числа, которые соответствуют маске 193*7?, делятся на 2068 без остатка и имеют кратную 7 сумму всех своих нетривиальных делителей.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им суммы всех их нетривиальных делителей.
Количество строк в таблице для ответа избыточно

def div(x):
  m = set()
  d = 2
  while d * d <= x:
    if x % d == 0:
      m |= {x // d, d}
    d += 1
  return m

from re import *

for i in range(19370// 2068 * 2068, 10 ** 9, 2068):
  if match(r'193.*7.$', str(i)) and sum(div(i)) % 7 == 0:
    print(i, i // 2068)

Чтобы оставить комментарий нужна авторизация

Печать