← 返回题目

题库练习金币(coin)

← 上一题下一题 →

A71880 | $金币(coin)$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

有 n 个人在争夺一枚金币。 所有人排成一队，然后位于第 1,1+k,1+2k,\dots,1+(⌊n/k⌋−1)k 个的人被淘汰，这里 ⌊n/k⌋ 为 n 除以 k 上取整，上取整操作会将一个小数变成大于或等于它的最小整数，如 ⌊33/5⌋=⌊6.6⌋=7。重复这一操作，直到仅剩一个人。最终剩下的这个人获得这枚金币。 小 Y 是所有人中最聪明的。他想知道，要想最终获得金币，一开始他应该站在第几个位置？

输入格式

一行包含两个正整数 n 和 k ，表示总人数以及淘汰时用到的参数。

输出格式

输出一行一个整数，表示小 Y 应该处于的初始队列中的位置。

输入输出样例

输入 #1

6 2

输出 #1

输入 #2

8 3

输出 #2

输入 #3

10000 2

输出 #3

样例输入 4 1919810 114514 样例输出 4 1919805 样例解释 对于样例 1：n=6，起初，队列 =[1,2,3,4,5,6]，因为 k=2，所以位于第 1,3,5 的人被淘汰，队列 =[2,4,6]，然后位于第 1,3 的人被淘汰，队列 =[4]，只剩下一个人，所以小 Y 一开始应该站在 4 号位置。 对于样例 2：n=8，起初，队列 =[1,2,3,4,5,6,7,8]，因为 k=3，所以位于 1,4,7 的人被淘汰，队列 =[2,3,5,6,8]，然后位于 1,4 的人被淘汰，队列 =[2,5,8]，然后位于 1 的人被淘汰，队列 =[5,8]，然后位于 1 的人被淘汰，队列 =[8]，只剩下一个人，所以小 Y 一开始应该站在 8 号位置。 数据范围 本题共有 12 个测试点，每个测试点 10 分。 对于全部测试点：2 \le n,k \le 10^{12}。 对于测试点 1 ：n=k=2。 对于测试点 2-4 ：n,k \le 1000。 对于测试的 5-8 ：k \le 1000000

C++ 编辑器

输入

输出