Наибольшим общим делителем пары натуральных чисел называется наибольшее из натуральных чисел, на которое каждое из чисел данной пары делится нацело. Для последовательности из некоторого количества натуральных чисел выполняется следующий алгоритм: пока в последовательности осталось не менее двух чисел берем два ее первых элемента, находим их наибольший общей делитель и удаляем их из исходной последовательности; затем все найденные наибольшие общие делители складываются. Полученное число является результатом выполнения описанного алгоритма.
Найдите последовательность, состоящую из N различных натуральных чисел, для которой результат применения описанного алгоритма будет равен K.
Формат ввода
В первой строке вводятся два натуральных разделенных одним пробелом натуральных числа N и K.
Формат вывода
В первой строке выведите N разделенных одиночными пробелами натуральных чисел – элементы искомой последовательности, если таковая существует. Если искомой последовательности нет, то выведите −1. Выводимые числа не должны превышать 1000000000. Если правильных ответов несколько, то выведите любой из них.
function gcd(a,b:integer):integer;
// Нахождение НОД
begin
while b<>0 do
begin
a:=a mod b;
var i:=b; b:=a; a:=i
end;
Result:=a
end;
procedure Shorter(var a,b:integer);
// "сокращатель" дроби
begin
var k:=gcd(a,b);
a:=a div k;
b:=b div k
end;
begin
var a,b:integer;
Writeln('Введите числитель и знаменатель дроби: ');
Read(a,b);
Write(a,'/',b,'='); Shorter(a,b); Writeln(a,'/',b)
end.
Тестовое решение:
Введите числитель и знаменатель дроби:
25 15
25/15=5/3