РЕШУ ЕГЭ — информатика

Задания

Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 16 получим: 16  =  16*1  =  8*2  =  4*4, множество разностей содержит числа 15, 6 и 0. Найдите все натуральные числа, принадлежащие отрезку [1 000 000; 2 000 000], у которых составленное описанным способом множество разностей будет содержать не меньше трёх элементов, не превышающих 100. В ответе перечислите найденные числа в порядке возрастания.

Ответ:

Решение. Заметим, что у каждого делителя числа имеется пара, например, пары делителей числа 16 будут выглядеть так: 1 и 16, 2 и 8, 4 и 4, всего пять различных делителей. Отсюда можно заключить, что имеет смысл перебирать возможные делители числа от единицы до корня от самого числа. Если разность результата целочисленного деления рассматриваемого в данный момент числа на его найденный делитель и этого делителя не будет превышать 100, в переменной count будем накапливать единицу. Если число count после работы вложенного цикла будет не меньше трёх  — выводим число на экран.

Приведём решение на языке Pascal.

var 
    count, i, j: longint;
    sqrtI: real;
begin
    for i := 1000000 to 2000000 do begin
        sqrtI := sqrt(i);
        count := 0;
        for j := 1 to round(sqrtI) do begin
            if (i mod j = 0) then begin
                if (((i div j) - j) < 101) then 
                    count := count + 1;
            end;
        end;
        if count > 2 then writeln(i);
        count := 0;
    end;
end.

Приведём решение на языке Python.

 
for i in range(1000000, 2000001):
    c = 0
    for d in range(int(i ** (0.5)), 899, -1):
        if(i % d == 0):
            if(abs(i / d - d) <= 100):
                c += 1
        if c > 2:
            print(i)
            break

В результате работы программа должна вывести следующее:

1113840

1179360

1208844

1499400

Приведём решение Бориса Савельева на языке Python.

for i in range (1000000,2000000+1):
    a = []
    k = int(i**0.5)+1
    for j in range (1,k):
        if i%j==0:
            if ((i//j)-j)<=100:
                a.append((i//j)-j)
    if len(a) >= 3:
        print(i)

Приведём решение Юрия Красильникова на языке Python.

def difs(n):
    d = []
    k=int(n**0.5) - 55 # небольшой запас
    while k**2 <= n:
        if n%k == 0: d.append(n//k - k)
        k += 1
    return len([x for x in d if x <= 100])
for n in range(1000000,2000001):
    if difs(n) >= 3: print(n)

№ п/п	№ задания	Ответ
1	33197	1113840 1179360 1208844 1499400

Ключ