Задача 6393. Источник: Поляков. Задание КИМ 25
(А. Богданов) Обозначим символом # последовательность цифр, сумма которых равна простому числу P. Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 1234# с разными P и делящиеся на (P+2)3. Если для какого-то P найдется несколько чисел, то запишите минимальное из них. В ответе запишите найденные числа в порядке возрастания. Справа от каждого числа соответствующее ему значение P.
Решение
Перебираем числа от 12342 до 1234999999 (минимальное и максимальное значение удовлетворяющее маске), проводя анализ на соответствие маске и условию задачи. Для хранения исключенных значений P создадим одноименный массив. Как и во многих других задачах, анализировать соответствие маске можно через целочисленные операции или через анализ строки, но, поскольку количество чисел для анализа очень велико, время выполнения программы в этих подходах будет отличаться в несколько раз. На Python анализ через строки работает более чем в три раза быстрее анализа через целочисленные операции, но и он на большинстве компьютеров будет выполняться более 10 минут. Поэтому лучше отдать предпочтение компилируемым языкам, где анализ через целочисленные операции работает в четыре раза быстрее анализа через строки. На C++ такое код работает около 10 секунд, а на PascalABC - около минуты. Обратите внимание, что, в отличие от большинства других задач, в данном случае функции анализа простоты числа могут передаваться значения 0 и 1, которые должны корректно обрабатываться.
Python анализ целочисленными операциями
def simple(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
p = []
for n in range(12342, 1235000000):
z = n
sm = 0
while z > 9999:
sm += z % 10
z //= 10
if z == 1234 and simple(sm):
if sm not in p and n % (sm + 2) ** 3 == 0:
p.append(sm)
print(n, sm)
Python анализ через строки
def simple(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
p = []
for n in range(12342, 1235000000):
if str(n)[:4] == '1234':
sm = 0
z = n
while z > 9999:
sm += z % 10
z //= 10
if simple(sm) and sm not in p and n % (sm + 2) ** 3 == 0:
p.append(sm)
print(n, sm)
PascalABC анализ целочисленными операциями
function simple(n: Integer): Boolean;
var
i: Integer;
begin
if n < 2 then
Result := False
else
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, pcount, i: Integer;
notp: Boolean;
p: array [1..100] of Integer;
begin
pcount := 0;
for n := 12342 to 1234999999 do
begin
z := n;
sum := 0;
while z > 9999 do
begin
sum := sum + z mod 10;
z := z div 10;
end;
if (z = 1234) and simple(sum) then
begin
notp := True;
for i := 1 to pcount do
if p[i] = sum then
begin
notp := False;
break;
end;
if notp and (n mod round(power(sum + 2, 3)) = 0) then
begin
pcount := pcount + 1;
p[pcount] := sum;
Writeln(n, ' ', sum);
end;
end;
end;
end.
PascalABC анализ через строки
function simple(n: Integer): Boolean;
var
i: Integer;
begin
if n < 2 then
Result := False
else
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, pcount, i: Integer;
notp: Boolean;
p: array [1..100] of Integer;
s: String;
begin
pcount := 0;
for n := 12342 to 1234999999 do
begin
s := IntToStr(n);
if s[:5] = '1234' then
begin
sum := 0;
z := n;
while z > 9999 do
begin
sum := sum + z mod 10;
z := z div 10;
end;
if simple(sum) then
begin
notp := True;
for i := 1 to pcount do
if p[i] = sum then
begin
notp := False;
break;
end;
if notp and (n mod round(power(sum + 2, 3)) = 0) then
begin
pcount := pcount + 1;
p[pcount] := sum;
Writeln(n, ' ', sum);
end;
end;
end;
end;
end.
C++ анализ целочисленными операциями
#include <iostream>
#include <cmath>
using namespace std;
bool simple(int n)
{
if (n < 2)
return false;
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int main()
{
int p[100];
int pcount = 0;
for (int n = 12342; n < 1235000000; n++)
{
int sum = 0;
int z = n;
while (z > 9999)
{
sum += z % 10;
z /= 10;
}
if (z == 1234 && simple(sum))
{
bool notp = true;
for (int i = 0; i < pcount; i++)
if (p[i] == sum)
{
notp = false;
break;
}
if (notp && n % (int)pow(sum + 2, 3) == 0)
{
p[pcount] = sum;
pcount++;
cout << n << " " << sum << endl;
}
}
}
}
C++ анализ через строки
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
bool simple(int n)
{
if (n < 2)
return false;
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int main()
{
int p[100];
int pcount = 0;
for (int n = 12342; n < 1235000000; n++)
{
string s = to_string(n);
if (s.substr(0, 4) == "1234")
{
int sum = 0;
int z = n;
while (z > 9999)
{
sum += z % 10;
z /= 10;
}
if (simple(sum))
{
bool notp = true;
for (int i = 0; i < pcount; i++)
if (p[i] == sum)
{
notp = false;
break;
}
if (notp && n % (int)pow(sum + 2, 3) == 0)
{
p[pcount] = sum;
pcount++;
cout << n << " " << sum << endl;
}
}
}
}
}
Ответ
12343000 3
123400269 17
123421875 23
1234200000 2
1234509249 29