Статья Автор: Лебедев Дмитрий Алексеевич

Задачи типа КЕГЭ-25 перед экзаменом

Задание 25-202601. Сумма крайних делителей: M оканчивается на 6 и кратно 7

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

Напишите программу, которая перебирает целые числа, бо́льшие 950 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на цифру 6 и при этом M кратно 7.

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значениями M. Например, для числа 20: M=2+10=12; M оканчивается на 2 и не кратно 7 — число не подходит.

#Задание 25-202601. Сумма крайних делителей: M оканчивается на 6 и кратно 7
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return [i for i in P if n % i == 0]
t0 = prt()
A, B = 950_000, 1_000_000
P = sieve(B)
k = 5
for n in range(A,B):
  ans = fact(n, P)
  m = 0
  if ans[0] < n :
    m = ans[0] + n//ans[0]
  if m % 10 == 6 and m % 7 == 0 :
    print(n,m)
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202602. Сумма всех нетривиальных делителей — точный квадрат

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

Напишите программу, которая перебирает целые числа, бо́льшие 600 000, в порядке возрастания и ищет среди них такие, для которых R является точным квадратом натурального числа (то есть R=k²для некоторого натурального k).

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значениями R.

# Задание 25-202602. Сумма всех нетривиальных делителей — точный квадрат
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return [i for i in P if n % i == 0]
def sfact(n, P) :
  pd = [i for i in P if n % i == 0]
  kd, sd = 1, 1
  for d in pd :
    i = 0
    while n % d == 0 :
      i += 1
      n = n // d
    kd *= (i+1)
    sd *= ((d**(i+1) - 1)//(d-1))
  return pd,kd, sd  
def check(n) :
  if n < 1 : return False
  m = int(n**0.5)
  if n in [(m-1)**2, m**2, (m+1)**2] : return True
  return False
t0 = prt()
A, B = 600_000, 650_000
P = sieve(B)
k = 5
for n in range(A,B):
  pd, kd, sd = sfact(n, P)
  sd -= (n + 1)
  if check (sd) :
    print(n,sd) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202603. Разность чётных и нечётных делителей

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

Напишите программу, которая перебирает целые числа, бо́льшие 1 200 000, в порядке возрастания и ищет среди них такие, для которых одновременно D>0 и D делится на 5.

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значениями D.

#Задание 25-202603. Разность чётных и нечётных делителей
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def kfact(n, P) :
  k2 = 0 
  while n % 2 == 0:
    k2 += 1
    n = n // 2
  pd = [i for i in P if n % i == 0]
  k1 = 1
  for d in pd :
    i = 0 
    while n % d == 0 :
      i += 1
      n = n// d
    k1 *= (i + 1)
  k2 = k1 * k2
  return pd, k1, k2
t0 = prt()
A, B = 1_200_000, 1_300_000
P = sieve(B)
k = 5
for n in range(A,B,2):
  pd, s1, s2 = kfact(n, P)
  D = s2 - s1
  if D > 0 and D % 5 == 0:
    print(n, D) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202604. Произведение двух простых, каждый содержит ровно одну цифру 7

Напишите программу, которая перебирает целые числа, бо́льшие 4 500 000, в порядке возрастания и ищет среди них такие, которые представимы в виде произведения двух простых чисел (не обязательно различных), в десятичной записи каждого из которых содержится ровно одна цифра 7.

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значение максимального простого числа в произведении.

#Задание 25-202604. Произведение двух простых, каждый содержит ровно одну цифру 7
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return [i for i in P if n % i == 0]
def check(n, pd):
  x = pd[0]
  if n == x * x and str(x).count('7') == 1 : return True
  if len(pd) != 2 : return False
  y = pd[1]
  if n == x * y and str(x).count('7') == 1 and str(y).count('7') == 1 : return True
  return False
t0 = prt()
A, B = 4_500_000, 5_000_000
P = sieve(B)
k = 5
for n in range(A,B):
  pd = fact(n, P)
  if check(n, pd) :
    print(n, pd[-1], pd) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202607. Сумма простых делителей — палиндром

Пусть S — сумма всех различных простых делителей целого числа, не считая самого числа. Если простых делителей нет (например, число равно 1), S=0.

Напишите программу, которая перебирает целые числа, бо́льшие 4 000 000, в порядке возрастания и ищет среди них такие, для которых S≠0 и S является палиндромом в десятичной записи (читается одинаково слева направо и справа налево).

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значение S.

#Задание 25-202607. Сумма простых делителей — палиндром
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return [i for i in P if n % i == 0]
def check(n, pd):
  if n == pd[0] : return False
  s = str(sum(pd))
  if s == s[::-1] : return True
  return False
t0 = prt()
A, B = 4_000_001, 4_100_000
P = sieve(B)
k = 5
for n in range(A,B):
  pd = fact(n, P)
  if check(n, pd) :
    print(n, sum(pd)) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202608. Восьмеричный вес 24 и ровно 4 делителя

Назовём восьмеричным весом натурального числа сумму его цифр в восьмеричной системе счисления.

Напишите программу, которая перебирает целые числа, бо́льшие 750 000, в порядке возрастания и ищет среди них такие, у которых одновременно:

восьмеричный вес равен 24;
число имеет ровно 4 различных натуральных делителя (с учётом 1 и самого числа).

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему сумму всех четырех натуральных делителей.

#Задание 25-202608. Восьмеричный вес 24 и ровно 4 делителя
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return [i for i in P if n % i == 0]
def check(n, pd):
  #if len(pd) > 2 : return 0, 0
  k, s = 1, 1
  for d in pd :
    i = 0
    while n % d == 0 :
      i += 1
      n = n // d
    k *= (i+1) 
    s *= ((d**(i+1) - 1)//(d - 1))
  return k, s
def check1(n, p=8, s=24):
  while n > 0 :
    s -= n % p
    n = n // p
  return s == 0  
t0 = prt()
A, B = 750_001, 760_000
C = [i for i in range(A, B) if check1(i) ]
P = sieve(B)
k = 5
for n in C:
  pd = fact(n, P)
  d, s = check(n, pd)
  if d == 4 :
    print(n, s) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру

Рассматриваются целые числа, принадлежащие отрезку [620000;720000], которые представимы в виде произведения трёх различных простых чисел, оканчивающихся в десятичной записи на одну и ту же цифру.

В ответе через пробел запишите два целых числа: количество таких чисел в отрезке и то из них, для которого разность наибольшего и наименьшего из соответствующих трёх простых множителей минимальна. Если таких чисел несколько — запишите наименьшее.

Для решения задачи применим метод моделирования ответа (это целесообразно, так как необходимо обработать отрезок в 100_000)
То есть перебираем тройки простых чисел, проверяя что они похдят.
Пусть x<y<z - такая тройка, тогда

x*x*x, x*y*y <=B
y%10 = x%10 и z%10 = x%10

Можно было бы вначале отобрать все такие тройки, отсортировать по минимальной разности (возможно код был бы проще)

#Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру
# вариант 1
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
t0 = prt()
A, B = 620_000, 720_000
P = sieve(B)
k = 0
for i in range(len(P)):
  x = P[i]
  if x**3 > B : continue
  for j in range(i+1, len(P)):
    y = P[j]
    if x % 10 != y % 10 or x*y*y > B : continue
    for ij in range(j + 1,len(P)):
      z = P[ij]
      xyz = x * y * z
      if x % 10 != z % 10 or xyz > B or xyz < A : continue
      if k == 0 or ((z - x) < ((ans[3] - ans[1]))) or ((z - x) == ((ans[3] - ans[1]))) and (xyz < ans[0]) : 
        ans =(xyz, x, y, z)
        #print(f'{ans=}')
      k += 1
print(k, ans)
print(f'time ={prt() - t0}')

#Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру
# вариант 2
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
t0 = prt()
A, B = 620_000, 720_000
P = sieve(B)
C =[]
for i in range(len(P)):
  x = P[i]
  if x**3 > B : continue
  for j in range(i+1, len(P)):
    y = P[j]
    if x % 10 != y % 10 or x*y*y > B : continue
    for ij in range(j + 1,len(P)):
      z = P[ij]
      xyz = x * y * z
      if x % 10 != z % 10 or xyz > B or xyz < A : continue
      C.append((z-x,xyz,x,y,z))
C.sort()
print(len(C), C[0])
print(f'time ={prt() - t0}')

Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу.

Найдите все натуральные числа, принадлежащие отрезку [3600000;5800000] и имеющие ровно три нетривиальных делителя.

В ответе через пробел запишите все найденные числа и их наибольшие нетривиальные делители

Формат ввода ответ
число делитель
число делитель

Задача почти устная, поскольку

три нетривиальный делителя означает, что всего делителей пять, а пять простое число значит искомое число есть
четвертая степень простого числа
в ответ надо записать все числа, значит их немного при большом интервале

#Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями
from time import process_time as prt
t0 = prt()
A, B = 3_600_000, 5_800_000
p0, p1 = A**0.25, B**0.25
print(f'{p0=} {p1=}')
for n in range(int(p0)+1, int(p1)+1):
  print(n**4, n**3)
print(f'time ={prt() - t0}')

Задание 25-202611. Сумма чётных делителей: M на 0, чётных делителей > 6

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

Напишите программу, которая перебирает целые числа, бо́льшие 2 200 000, в порядке возрастания и ищет среди них такие, для которых одновременно выполнено:

M оканчивается на цифру 0;
число чётных делителей (не считая самого числа) больше 6.

В ответе запишите пять строк в порядке возрастания найденных чисел. В каждой строке сначала найденное число, затем через пробел соответствующее ему значение M.

#Задание 25-202611. Сумма чётных делителей: M на 0, чётных делителей > 6
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def kfact(n, P) :
  k2 = 0 
  while n % 2 == 0:
    k2 += 1
    n = n // 2
  pd = [i for i in P if n % i == 0]
  k1, s1 = 1, 1
  for d in pd :
    i = 0 
    while n % d == 0 :
      i += 1
      n = n// d
    k1 *= (i + 1)
    s1 *= ((d**(i+1) - 1)//(d-1))
  kd2 = k1 * k2
  sd2 = s1 * (2**(k2 + 1) - 1) - s1
  return pd, kd2, sd2
t0 = prt()
A, B = 2_200_002, 2_300_000
P = sieve(B)
k = 5
for n in range(A,B, 2):
  pd, kd2, sd2 = kfact(n, P)
  sd2 -= n
  kd2 -= 1
  if kd2 > 6 and sd2 % 10 == 0:
    print(n, sd2) 
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Задание 25-2026012. Числа с ровно 12 делителями в [185 000; 185 100]

Найдите все натуральные числа, принадлежащие отрезку [185000;185100] и имеющие ровно 12 различных натуральных делителей (с учётом единицы и самого числа).

Для каждого найденного числа определите сумму всех его делителей.

В ответе запишите все найденные числа в порядке возрастания, через пробел от числа соответствующее ему значение суммы делителей этого числа. Каждую пару чисел записывайте в отдельной строке.

#Задание 25-2026012. Числа с ровно 12 делителями в [185 000; 185 100]
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def kfact(n, P) :
  pd = [i for i in P if n % i == 0]
  k, s = 1, 1
  for d in pd :
    i = 0 
    while n % d == 0 :
      i += 1
      n = n// d
    k *= (i + 1)
    s *= ((d**(i+1) - 1)//(d-1))
  return pd, k, s
t0 = prt()
A, B = 185_000, 185_101
P = sieve(B)
for n in range(A,B):
  pd, kd, sd = kfact(n, P)
  if kd == 12 :
    print(n, sd) 
print(f'time ={prt() - t0}')

Задание 25-202613. M оканчивается на 8, сумма цифр n кратна 7

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

Напишите программу, которая перебирает целые числа, бо́льшие 1 200 000, в порядке возрастания и ищет среди них такие, для которых одновременно выполнено:

значение M оканчивается на цифру 8;
сумма цифр самого числа в десятичной записи кратна 7.

В ответе запишите первые пять найденных чисел в порядке возрастания, через пробел от каждого числа его значение M. Каждая пара (число M) записывается в отдельной строке.

#Задание 25-202613. M оканчивается на 8, сумма цифр n кратна 7
from time import process_time as prt
def sieve(n):
  M = [0,0,1]+[1,0] * (n//2)
  for d in range(3, int(n**.5)+1, 2):
    if M[d] :
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2))
  return [i for i in range(n) if M[i]]    
def fact(n, P) :
  return  [i for i in P if n % i == 0]
def check(M, n):
  if M % 10 !=8 : return 0
  s = sum(int(a) for a in str(n))
  if s % 7 == 0 : return True
  return False
t0 = prt()
A, B = 1_200_001, 1_300_000
P = sieve(B)
k = 5
for n in range(A,B):
  pd = fact(n, P)
  if n == pd[0] : continue
  M = pd[0] + n // pd[0]
  if check(M, n) :
    print(n, M)
    k -= 1
    if k == 0 : break
print(f'time ={prt() - t0}')

Печать