Задание №25
ЕГЭ-2023. Задание 25
Тема: Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации. Время выполнения 20 минут.
Решение задания № 25 ЕГЭ-2023. Демо.
Условие задачи:
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10^10, найдите все числа, соответствующие маске 1?2139*4, делящиеся на 2023 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 2023.
решение я.п. Python:
kp='0123456789'
#вместо звездочки - пустота:
for x in kp:
n=int(f'1{x}21394')
if n%2023==0:
print(n,n//2023)
#нет ни одного числа
for x in kp:
for y in kp:
for z in kp:
n=int(f'1{x}2139{y}{z}4')
if n%2023==0:
print(n,n//2023)
# одна '*': чисел, отвечающих условию нет, поэтому изменяем фрагмент кода, что выше - добавляем в шаблон {z}
for x in kp:
for y in kp:
for z in kp:
for w in kp:
n=int(f'1{x}2139{y}{z}{w}4')
if n%2023==0:
print(n,n//2023)
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
int main()
{
set <int> kp={0,1,2,3,4,5,6,7,8,9};
unsigned int n;
for(int x:kp)
for(int y:kp)
for(int z:kp){
n = 1e08 + x*1e07 + 2139*1e03 + y*100 +z*10 +4;
if (n%2023==0)
cout<<n<<' '<<n/2023<<endl;
}
for(int x:kp)
for(int y:kp)
for(int z:kp)
for(int w:kp){
n = 1e09 + x*1e08 + 2139*1e04 + y*1e03 +z*100 +w*10 +4;
if (n%2023==0)
cout<<n<<' '<<n/2023<<endl;
}
return 0;
}
Ответ:
162139404 80148
1321399324 653188
1421396214 702618
1521393104 752048
Задание № 25. Апробация 03022023. внешний файл
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
– символ «?» означает ровно одну произвольную цифру;
– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300405.
Среди натуральных чисел, не превышающих 10^8, найдите все числа, соответствующие маске 12?3*46, делящиеся на 129 без остатка.
В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 129.
Ответы и решение
1 1273746 9874
2 12032346 93274
2 12135546 94074
2 12238746 94874
2 12432246 96374
2 12535446 97174
2 12638646 97974
2 12832146 99474
2 12935346 100274
# нет ни одного числа при "*" - пустая последовательность
kf='0123456789'
for x in kf:
for y in kf:
n = int(f'12{x}3{y}46')
if n%129==0:
print('1',n,n//129)
for x in kf:
for y in kf:
for z in kf:
n = int(f'12{x}3{y}{z}46')
if n%129==0:
print('2',n,n//129)
Другие задачи
Задача 1. (Ушаков Д.)
Назовём нетривиальным делителем числа X такой натуральный делитель числа X, который отличен от 1 и от самого числа.
Напишите программу, которая ищет среди целых чисел, больших 150 000, такие, что среди их нетривиальных делителей есть такой, который оканчивается на 2 или на 3, и при этом больше 4. Найдите 6 таких наименьших чисел.
В ответе для каждого найденного числа запишите само число и наибольший нетривиальный делитель, оканчивающийся на 2 или на 3, и при этом больше 4.
Например, среди чисел, больших 1, наименьшие три таких числа — 24, 26 и 36. Поэтому при таких данных таблица на экране должна содержать следующие значения:
24; 12
26; 13
36; 12
Ответы и решение
150003 7143
150004 75002
150006 75003
150007 143
150008 37502
150009 50003
я.п. Python:
def nd(x):
d=5
mx=0
for i in range(d,x//2+1):
if (i%10==2 or i%10==3) and x%i==0:
mx=max(mx,i)
return(mx)
a=150001;
n=6
k=0
while k<n:
y=nd(a)
if y!=0:
k +=1
print(a,y)
a +=1
я.п. C/C++
#include <bits/stdc++.h>
using namespace std;
int nd(int x){
int d=5,mx=0;
for(int i=d;i<x/2+1;i++){
if((i%10==2 || i%10==3)&& x%i==0){
mx=max(mx,i);
}
}
return mx;
}
int main()
{
int a = 150001,n=6,k=0,y;
while(k<n){
y = nd(a);
if (y!=0){
k +=1;
cout<<a<<' '<<y<<endl;
}
a +=1;
}
return 0;
}
Задача 2. (Евич Л.Н.)
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [50 000 000; 60 000 000], числа, имеющие ровно шесть различных натуральных делителей (не считая единицы и самого числа), среди которых есть число 911. В ответе за пишите сначала количество таких чисел, а затем наименьшее из них.
Ответ и решение
2489; 50002057
я.п. Python:
mn=10**8
a=50_000_000
b=60_000_000
n=50000235
k=0
while n<=b:
q=int(n**0.5)
if q*q!=n and n%911==0:
dels=[]
cnt=0
for j in range(2,int(n**0.5)+1):
if n%j==0:
cnt +=2
dels.append(j)
dels.append(n//j)
if cnt>6: break
if cnt==6:
k +=1
mn=min(mn,n)
n +=1
print(k,mn)
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
int main()
{
unsigned int mn=1e08,a=5*1e07,b=6*1e07,n,k=0,q;
n=50000235;
while(n<=b){
q = (int)pow(n,0.5);
if (q*q!=n && n%911==0){
int cnt=0;
for(int j=2;j<(int)pow(n,0.5)+1;j++){
if(n%j==0){
cnt +=2;
if(cnt>6)
break;
}
}
if (cnt==6){
k +=1;
mn = min(mn,n);
}
}
n +=1;
}
cout<<k<<' '<<mn<<endl;
return 0;
}
Решение задания № 25 ЕГЭ прежних лет
Данная задача (судя по условию задачи) решается довольно просто... НО... Если решать ее простым перебором, то задача будет выполняться довольно долго. Поэтому необходимо применить методы сокращения перебора:
Отсечь все простые числа (первое число интервала - простое число), так как они имеют всего два делителя: само число и единицу. В условии задачи сказано, что такие числа не соответствуют условию задачи.
Искать не все делители числа, а только - два. То есть, останавливать поиск, как только количество делителей превышает k=2.
Так как нечетные числа имеют делители тоже нечетные, то делители числа можно искать с шагом, равным 2. Например, допустим, первый делитель -3, тогда следующий делитель должен быть взят - 5 и т.д. А Четные числа, у которых первый делитель - 2, а следующий может быть как четным, так и нечетным числом. Следовательно, напрашивается метод, при котором необходимо делители чисел для четных и нечетных чисел искать отдельно.
И, еще одно наблюдение. Если число имеет только два делителя, то оба делителя - простые числа. Примеры: число четное 22 имеет только два делителя- 2 и 11; четное 14 - 2 и 7; нечетное 21 - 3 и 7; нечетное 33 - 3 и 11... Следовательно, определив первый делитель, проверяем будет ли второе число (на примере числа 21 - первый делитель 3, а 21/3=7 - второе число) простым. Если да, то мы нашли такое число. Для того, чтобы убедиться в этом, проделайте вычисления над большим количеством чисел... И, если число имеет больше делителей, чем 2, то второе число не будет простым... Например, возьмем число 12 (делители этого числа - 2, 3, 4, 6): первый делитель - 3. Тогда, 12/3=4, а число 4 - не простое...
И, последнее, сортировать в порядке возрастания итоги решения не надо, так как значения делителей возрастают с возрастанием чисел.
using namespace std;
bool prost(long x){long del=3; while(del<=int(sqrt(x))){ if(x%del==0) return 0; del +=2; }return 1;}
int main(){ long k, d=2, dd, y=a; while(y<=b){//работа с четными числами if(y%2==0){ k=0; while(y%d==0){ k++; d++; } if(k>=2){ y++; d=2; continue; } else { dd = y/(d-1); if(prost(dd)){ cout<<d-1<<' '<<dd<<endl; } } } else{ //далее работа с нечетными числами if(prost(y)){ y++; continue; } else{ while(y%d!=0){ d++; } dd = y/d; if(prost(dd)){ cout<<d<<' '<<dd<<endl; } } } d=2; y++; } return 0;}
function prost(x: longint):Boolean;var del: LongInt;begin del:=3; while del<=Trunc(Sqrt(x)) do begin if x mod del =0 then begin prost:=False; Exit; end; del:=del + 2; end; prost:=True;end;
begin y:=a; while y<=b do begin if y mod 2 = 0 then begin d:=2; k:=0; while y mod d =0 do begin k:=k + 1; d:=d + 1; end; if k>=2 then begin y:=y+1; d:=2; Continue; end else begin dd:=y div (d-1); if prost(dd) then begin Writeln(d-1,' ',dd); k:=0; end; end; end else begin if prost(y) then begin y:=y+1; Continue; end else begin while y mod d <>0 do d:=d+1; dd:=y div d; if prost(dd) then begin Writeln(d,' ',dd); end; end; end; y:=y+1; d:=2; end;end.