Задача 6408. Источник: Поляков. Задание КИМ 25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300425.
Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 1?359*0, которые делятся на 4019 без остатка и у которых сумма цифр – простое число. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа – результат его деления на 4019.
Решение
Ищем первое число кратное 4019 после минимального значения удовлетворяющего маске 103590 и перебираем числа с данным шагом до максимального значения удовлетворяющего маске 1935999990. Для анализа данного диапазона чисел достаточно использования 32-битного целого. Остальные числа до верхней границы задачи маске соответствовать не будут, а их более 80%. Для чисел удовлетворяющих шаблону находим сумму цифр и проверяем ее на простоту. Анализировать соответствие числа маске можно через целочисленные операции или через анализ строки. На 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 = 103590
while z % 4019 != 0:
z += 1
for n in range(z, 1935999991, 4019):
if n % 10 == 0:
z = n // 10
while z > 99999:
z //= 10
if z // 10000 == 1 and z % 1000 == 359:
sm = 0
z = n
while z > 0:
sm += z % 10
z //= 10
if simple(sm):
print(n, n // 4019)
Python анализ через строки
def simple(n):
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
z = 103590
while z % 4019 != 0:
z += 1
for n in range(z, 1935999991, 4019):
s = str(n)
if s[0] == '1' and s[2:5] == '359' and s[-1] == '0':
sm = 0
z = n
while z > 0:
sm += z % 10
z //= 10
if simple(sm):
print(n, n // 4019)
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 = 103590
while z % 4019 != 0:
z += 1
for n in range(z, 1935999991, 4019):
if fnmatch(str(n), '1?359*0'):
sm = 0
z = n
while z > 0:
sm += z % 10
z //= 10
if simple(sm):
print(n, n // 4019)
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, sum: Integer;
begin
n := 103590;
while n mod 4019 <> 0 do
n := n + 1;
while n <= 1935999990 do
begin
if n mod 10 = 0 then
begin
z := n div 10;
while z > 99999 do
z := z div 10;
if (z div 10000 = 1) and (z mod 1000 = 359) then
begin
sum := 0;
z := n;
while z > 0 do
begin
sum := sum + z mod 10;
z := z div 10;
end;
if simple(sum) then
Writeln(n, ' ', n div 4019);
end;
end;
n := n + 4019;
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, sum, z: Integer;
s: String;
begin
n := 103590;
while n mod 4019 <> 0 do
n := n + 1;
while n <= 1935999990 do
begin
s := IntToStr(n);
if (s[1] = '1') and (s[3:6] = '359') and (s[s.Length] = '0') then
begin
sum := 0;
z := n;
while z > 0 do
begin
sum := sum + z mod 10;
z := z div 10;
end;
if simple(sum) then
Writeln(n, ' ', n div 4019);
end;
n := n + 4019;
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 = 103590;
while (z % 4019 != 0)
z++;
for (int n = z; n < 1935999991; n += 4019)
{
if (n % 10 == 0)
{
int z = n / 10;
while (z > 99999)
z /= 10;
if (z / 10000 == 1 && z % 1000 == 359)
{
int sum = 0;
z = n;
while (z > 0)
{
sum += z % 10;
z /= 10;
}
if (simple(sum))
cout << n << " " << n / 4019 << endl;
}
}
}
}
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 = 103590;
while (z % 4019 != 0)
z++;
for (int n = z; n < 1935999991; n += 4019)
{
string s = to_string(n);
if (s [0] == '1' && s.substr(2, 3) == "359" && s[s.length() - 1] == '0')
{
int sum = 0;
z = n;
while (z > 0)
{
sum += z % 10;
z /= 10;
}
if (simple(sum))
cout << n << " " << n / 4019 << endl;
}
}
}
Ответ
193595230 48170 1035977630 257770 1135930160 282640 1335955790 332410 1835959580 456820 1935952300 481700