[常州市赛 2025] 金币

Luogu

IDLGB4395

Time1000ms

Memory512MB

DifficultyP5

数学2025数论江苏科创活动小学活动

有 $n$ 个人在争夺一枚金币。所有人排成一队，然后位于第 $1,1+k,1+2k,\cdots,1+\left(\left\lceil\dfrac nk\right\rceil−1\right)k$ 个的人被淘汰，这里 $\left\lceil\dfrac nk\right\rceil$ 为 $n$ 除以 $k$ 上取整，上取整操作会将一个小数变成大于或等于它的最小整数，如 $\left\lceil\dfrac{33}5\right\rceil=\left\lceil6.6\right\rceil=7$。重复这一操作，直到仅剩一个人。最终剩下的这个人获得这枚金币。小 Y 是所有人中最聪明的。他想知道，要想最终获得金币，一开始他应该站在第几个位置？ ## Input 一行包含两个正整数 $n$ 和 $k$，表示总人数以及淘汰时用到的参数。 ## Output 输出一行一个整数，表示小 Y 应该处于的初始队列中的位置。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/1412>。数据为民间数据。 ## Note ### 样例 $\textbf 1$ 解释起初，队列 $=[1,2,3,4,5,6]$，因为 $k=2$，所以位于第 $1,3,5$ 的人被淘汰，队列 $=[2,4,6]$，然后位于第 $1,3$ 的人被淘汰，队列 $=[4]$，只剩下一个人，所以小 Y 一开始应该站在 $4$ 号位置。 ### 样例 $\textbf 2$ 解释起初，队列 $=[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$ 个数据。对于全部数据，$2\le n,k\le10^{12}$。 |测试点编号|特殊性质| |:-:|:-:| |$1$|$n=k=2$| |$2\sim4$|$n,k\le 10^3$| |$5\sim8$|$k\le 10^6$| |$9\sim12$|无|

Samples

Input #1

6 2

Output #1

Input #2

8 3

Output #2

Input #3

10000 2

Output #3

Input #4

1919810 114514

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[常州市赛 2025] 金币",
    "description": {
      "content": "有 $n$ 个人在争夺一枚金币。 所有人排成一队，然后位于第 $1,1+k,1+2k,\\cdots,1+\\left(\\left\\lceil\\dfrac nk\\right\\rceil−1\\right)k$ 个的人被淘汰，这里 $\\left\\lceil\\dfrac nk\\right\\rceil$ 为 $n$ 除以 $k$ 上取整，上取整操作会将一个小数变成大于或等于它的最小整数，如 $\\left\\l",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4395"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个人在争夺一枚金币。\n\n所有人排成一队，然后位于第 $1,1+k,1+2k,\\cdots,1+\\left(\\left\\lceil\\dfrac nk\\right\\rceil−1\\right)k$ 个的人被淘汰，这里 $\\left\\lceil\\dfrac nk\\right\\rceil$ 为 $n$ 除以 $k$ 上取整，上取整操作会将一个小数变成大于或等于它的最小整数，如 $\\left\\l...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments