QUEUE
시간 제한0.5초메모리 제한1024 MB
여러 번의 삽입 과정을 거쳐 정확히 N명이 되는 가장 작은 초기 대기열 인원을 구한다.
문제
Няколко ученици, но най-малко двама, са се наредили един след друг на опашка и чакат да ги ваксинират против ковид, което все още не е започнало. Изведнъж идва група закъснели ученици, които се пререждат, като броят им е точно такъв, че един от тях застава между учениците от последната двойка на опашката, следващият от групата отива напред, като пропуска K места между поредни двойки ученици и застава между учениците от следващата двойка. По същия начин се наместват и останалите от новодошлата група. След време идва още една група ученици, които правят същото – пререждат се, като застават по описания начин между съответни двойки от ново-оформената опашка. Няколко пъти се повтаря идването на нови групи ученици и те правят същото. Накрая, точно преди да започне ваксинирането, в опашката има N ученици (вижте по-долу пояснението към пример 1).
Напишете програма queue, която намира колко най-малко ученици е възможно да е имало първоначално на опашката.
입력
Две цели числа, отделени с интервал − стойностите на N и K.
출력
Едно цяло число, равно на най-малкия брой ученици, които е възможно да са били първоначално на опашката.
제한
- 1 < N < 1016
- 0 ≤ K < 100
힌트
Пояснение към пример 1: Ако първоначално на опашката е имало 5 ученици, нека да ги номерираме отзад-напред така: 1 2 3 4 5. Идва първа група с двама ученици и те се вместват между 1 и 2, и между 3 и 4. Така стават 7 ученици. Нека да ги преномерираме: 1 2 3 4 5 6 7. Идва следваща група с трима ученици и те се вместват между 1 и 2, между 3 и 4, и между 5 и 6. Така на опашката вече има 10 ученици и това е точно, колкото е дадено във входа на примера.
Не е възможно да е имало първоначално по-малко от 5 ученици. За да обосновем това, трябва да разгледаме възможността да е имало 4 ученици: 1 2 3 4. Идват двама (наместват се между 1 и 2, и между 3 и 4) и стават 6 ученици: 1 2 3 4 5 6. Сега идват трима ученици (наместват се между 1 и 2, между 3 и 4, и между 5 и 6) и стават 9 ученици: 1 2 3 4 5 6 7 8 9. Сега идват 4 ученици, които могат да се наместят и стават 13. След това, каквито и групи ученици да идват, общият брой ще е по-голям от 10.
Ако първоначално е имало 3 ученици, при идване на всяка следваща група броя на учениците в опашката се изменят така: 4, 6, 9, 13 и т.н., т.е., не е възможно да станат 10. Аналогично обосноваваме, че не е възможно първоначалният брой да е бил равен на 2.