Ряд состоит из натуральных чисел от 1 до n. задается натуральное число k и выполняется один или несколько шагов по удалению каждого k-ого числа в этом ряду. на очередном шаге оставшиеся числа просматриваются в возрастающем порядке, и каждое k-е число удаляется. если после очередного шага осталось меньше k чисел, то процесс удаления чисел завершается. необходимо определить, на каком шаге будет удалено число n, или выяснить, что оно не будет удалено до завершения процесса. например, пусть n = 13, k = 2. • на первом шаге будут удалены числа 2, 4, 6, 8, 10 и 12, останутся числа 1, 3, 5, 7, 9, 11 и 13. • на втором шаге будут удалены числа 3, 7 и 11, останутся числа 1, 5, 9 и 13. • на третьем шаге будут удалены числа 5 и 13, останутся числа 1 и 9. • на четвертом шаге будет удалено число 9, останется число 1. поскольку осталось одно число, процесс завершается. таким образом, число 13 будет удалено на третьем шаге. требуется написать программу, которая по заданным числам n и k определяет, на каком шаге будет удалено число n. формат ввода первая строка входных данных содержит целое число n (3 ≤ n ≤ 10**18). вторая строка входных данных содержит целое число k (2 ≤ k ≤ 100, k < n). формат вывода требуется вывести одно целое число — номер шага, на котором будет удалено число n, или число 0, если число nне будет удалено. пример 1 ввод вывод 13 2 3 пример 2 ввод вывод 3 2 2
Для того, чтобы в последовательности из n элементов удалить последний путем вычеркивания каждого k-го элемента, n должно быть кратно k - это и есть условие успешного удаления. Запишем его в виде n mod k = 0, где mod - операция получения остатка целочисленного деления n на k.
Если n не кратно k, то будут вычеркнуты [n / k] элементов последовательности. Здесь [ ] - обозначение операция взятия целой части числа (антье), введенное в математику К. Гауссом.
После вычеркивания [n / k] элементов, в последовательности останется n₁ = n - [n / k] элементов. Если повторять этот процесс, то либо на шаге m будет вычеркнут последний элемент, либо количество элементов станет меньше k.
Рассмотрим приведенный в задании пример.
n=13, k=2
n mod k ≠ 0, поэтому полагаем n₁ = n - [n / k] = 13 - [13 / 2] = 13 - 6 = 7
n₁ mod k ≠ 0, поэтому полагаем n₂ = n₁ - [n₁ / k] = 7 - [7 / 2] = 7 - 3 = 4
n₂ mod k = 0, следовательно на третьем шаге вычеркивания мы получим нужный результат.
PascalABC.NET 3.4.2, сборка 1884 от 24.11.2018Внимание! Если программа не работает, обновите версию!begin
var (n, k) := ReadInteger2;
var m := 0;
while n >= k do
begin
if n mod k = 0 then
begin
Print(m + 1);
exit
end
else
begin
n := n - n div k;
Inc(m)
end
end;
Print(0)
end.
Пример13 23Вводить данные можно как через пробел, так и построчно