favorite We need a little bit of your help to keep things running, click on this banner to learn more

Josephus problem

Josephus problem

Legend has itthatJosephus-a famoushistorianof the first century-survivedandbecame famousmathematicalgenius.Duringthe Jewishwar, hein thesquadof41Jewishwarriorwasdrivenby the Romansina cave.Preferringsuicidecaptivity,the soldiersdecided tostand ina circleandconsistentlykilleachthirdofthe livinguntil,until there isa single man.However,Joseph, alongwith oneof hissupportersfeltlikethe end of thesenseless-hequicklyfigured outthe savingspacein a viciouscircle,whichhas placed himselfandhis companion.Andjustso weknowits history.

Inourversion, westartwithwhatis built interms ofNpeople,numbered from1 toN,andwillexcludeeveryk-thuntilthen,untilonly onepersonsurvives.(For example, ifN = 10, k =3, thefirstdiethird,thenthe 6-thand then9-th,then 2-nd,thenthe 7-th,thenthe 1-st,thenthe 8-th, with theit - the5-th,andthenthe 10-th.Thus,escapethe 4-th.)


In the inputfileare givenpositive integersN and k. 1N500, 1k100.


The outputfileshouldcontaina single number- the number ofsurvivinghumans.

Time limit 1 second
Memory limit 64 MiB
Input example #1
10 3
Output example #1