Задача 6426. Источник: Поляков. Задание КИМ 25
(Р. Ягафаров) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300425.
Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 12?5*5??, которые представляют собой произведение двух различных простых чисел и делятся на 311 без остатка. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа – результат его деления на 311.
Решение
Начиная с минимального числа соответствующего маске 1205500, найдем минимальное число, кратное 311 и далее будем перебирать числа с данным шагом до максимального числа удовлетворяющего маске 12959599. Каждое число будем сначала анализировать на соответствие маске, а потом на делители, т.к. проверка соответствия маске будет выполняться быстрее. Проверку соответствия числа маске можно осуществлять через целочисленные операции или через анализ строки. При анализе через строки на Python возможно использование библиотеки fnmatch.
Python анализ целочисленными операциями
def simple(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
z = 1205500
while z % 311 != 0:
z += 1
for n in range(z, 12959600, 311):
if n // 100 % 10 == 5:
z = n // 1000
while z > 9999:
z //= 10
if z // 100 == 12 and z % 10 == 5:
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
if simple(i) and simple (n // i):
print(n, n // 311)
else:
break;
Python анализ через строки
def simple(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
z = 1205500
while z % 311 != 0:
z += 1
for n in range(z, 12959600, 311):
s = str(n)
if s[:2] == '12' and s[3] == '5' and s[-3] == '5':
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
if simple(i) and simple (n // i):
print(n, n // 311)
else:
break;
Python анализ с использованием библиотеки fnmatch
def simple(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
from fnmatch import fnmatch
z = 1205500
while z % 311 != 0:
z += 1
for n in range(z, 12959600, 311):
if fnmatch(str(n), '12?5*5??'):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
if simple(i) and simple (n // i):
print(n, n // 311)
else:
break;
PascalABC анализ целочисленными операциями
function simple(n: Integer): Boolean;
var
i: Integer;
begin
Result := True;
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
begin
Result := False;
break;
end;
end;
var
n, z, i: Integer;
begin
n := 1205500;
while n mod 311 <> 0 do
n := n + 1;
while n <= 12959599 do
begin
if n div 100 mod 10 = 5 then
begin
z := n div 1000;
while z > 9999 do
z := z div 10;
if (z div 100 = 12) and (z mod 10 = 5) then
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
if simple(i) and simple(n div i) then
Writeln(n, ' ', n div 311)
else
break;
end;
n := n + 311;
end;
end.
PascalABC анализ через строки
function simple(n: Integer): Boolean;
var
i: Integer;
begin
Result := True;
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
begin
Result := False;
break;
end;
end;
var
n, i: Integer;
s: String;
begin
n := 1205500;
while n mod 311 <> 0 do
n := n + 1;
while n <= 12959599 do
begin
s := IntToStr(n);
if (s[:3] = '12') and (s[4] = '5') and (s[s.Length - 2] = '5') then
for i := 2 to round(sqrt(n)) do
if n mod i = 0 then
if simple(i) and simple(n div i) then
Writeln(n, ' ', n div 311)
else
break;
n := n + 311;
end;
end.
C++ анализ целочисленными операциями
#include <iostream>
#include <cmath>
using namespace std;
bool simple(int n)
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int main()
{
int z = 1205500;
while (z % 311 != 0)
z++;
for (int n = z; n < 12959600; n += 311)
{
if (n / 100 % 10 == 5)
{
int z = n / 1000;
while (z > 9999)
z /= 10;
if (z / 100 == 12 && z % 10 == 5)
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
if (simple(i) && simple(n / i))
cout << n << " " << n / 311 << endl;
else
break;
}
}
}
}
C++ анализ через строки
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool simple(int n)
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int main()
{
int z = 1205500;
while (z % 311 != 0)
z++;
for (int n = z; n < 12959600; n += 311)
{
string s = to_string(n);
if (s.substr(0, 2) == "12" && s[3] == '5' && s[s.length() - 3] == '5')
{
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
if (simple(i) && simple(n / i))
cout << n << " " << n / 311 << endl;
else
break;
}
}
}
Ответ
12056537 38767
12153569 39079
12451507 40037
12459593 40063
12655523 40693
12854563 41333