+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حسنی و $n - 1$ نفر از دوستانش دور یک دایره نشستند و شروع به انجام بازی اتل‌متل $k$توله می‌کنند. شیوه انجام بازی این جوری هست که حسنی به عنوان نفر اول می‌گوید "سلام!". بعد از آن در هر مرحله نفر $k$ تا جلوتر نفر قبلی می‌گوید "سلام!". این روال ادامه دارد تا دوباره نوبت حسنی شود و آن موقع بازی تموم می‌شود. حالا حسنی می‌خواهد بداند که این بازی چند مرحله طول می‌کشد و از آن‌جا که خیلی سرگرم بازی شده، از شما می‌خواهد تا جواب را به او بگویید. # ورودی در خط اول ورودی $n$ و $k$ آمده‌ است. $$1 \le k \le n \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد مراحلی را که طول می‌کشد تا دوباره نوبت حسنی شود را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 2 ``` ## خروجی نمونه ۱ ``` 5 ``` اگر افراد دور دایره را از $1$ تا $5$ شماره‌گذاری کنیم به طوری که حسنی شماره یک را بگیرد طبق چنین روندی دوباره نوبت حسنی می‌شود: $$(1, 3, 5, 2, 4, 1)$$ ## ورودی نمونه ۲ ``` 6 2 ``` ## خروجی نمونه ۲ ``` 3 ``` در این حالت افرادی که سلام می‌کنند چنین شماره‌هایی را دارند: $$ (1, 3, 5, 1) $$ ## ورودی نمونه ۳ ``` 6 6 ``` ## خروجی نمونه ۳ ``` 1 ``` در این حالت نفر $k$تا بعدی حسنی خود حسنی است! ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> سعی کنید روند بازی را به صورت ساده، جوری که بتوانید کد آن را بزنید، در بیاورید. برای مثال در سوال آمده است "تا زمانی که نوبت دوباره به حسنی نرسیده‌است، بازی ادامه دارد." که این همان *حلقه* است. (با [این لینک](https://fullkade.com/1397/08/programming-loop/) می‌توانید بیشتر با حلقه آشنا شوید.) </details> <details class="blue"> <summary> راهنمایی ۲ </summary> فرض کنید دو متغیر *cnt* و *cur* دارید که در هر مرحله *cnt* برابر تعداد مراحل تا الان است و *cur* برابر اینکه اخرین نفری که گفت "سلام" چه کسی است. برای مثال‌ها مراحل را اجرا کنید و مقدار *cur* و *cnt* را در هر مرحله یادداشت کنید. فرض کنید که افراد را از ۰ تا $n-1$ شماره‌گذاری کردیم و حسنی شماره ۰ است. مثلا برای ورودی نمونه ۲ که $n = 6$ و $k=2$ است به این شکل مقدار‌های متغیر بعد از هر مرحله تغییر می‌کند. | cnt | cur | |:---:|:---:| | ۱ | ۰ | | ۲ | ۲ | | ۳ | ۴ | و بعد از مرحله ۳ دوباره حسنی را می‌بینیم و بازی تمام می‌شود. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> قسمت اصلی الگوریتم، یعنی شبیه‌سازی کردن بازی، از یک *حلقه* تشکیل شده است و دو متغیر *cnt* و *cur*که حلقه تا زمانی که بازی تمام نشده است، اجرا می‌شود. شبه کد الگوریتم: ``` assign 0 to *cnt* assign 0 to *cur* while true : increase value of *cnt* by one update value of *cur* if *cur* = 0: break ``` منظور از دستور `break` این است که از حلقه `while` بیرون بیاید و منظور از `while true` یعنی تا زمانی که به دستور `break` نرسیده است، حلقه را تکرار کند و منظور از `assign 0 to *cnt*` این است که مقدار متغیر `cnt` را برابر صفر بکن. </details> <details class="blue"> <summary> راه حل </summary> می‌توانید مشاهده کنید که بعد هر مرحله *cnt* یک واحد زیاد می‌شود و *cur* باید برابر *k*-امین نفر جلو باشد. در صورتی که افراد را به ترتیب از 0 تا $n-1$ شماره گذاری کنید و حسنی 0 باشد. بعد هر مرحله *cur* به علاوه *k* می‌شود و سپس به پیمانه *n* باقی مانده گرفته می‌شود. ``` assign 0 to *cnt* assign 0 to *cur* while true : increase value of *cnt* by one assign (*cur* + *k*) to *cur* assign (*cur* mod *n*) to *cur* if *cur* = 0: break ``` </details>