「CZOI-R1」进制

Luogu
IDLGP10797
Time1500ms
Memory512MB
DifficultyP3
O2优化位运算
你有一个数 $x$,你需要对它进行 $n$ 次操作。 每次操作,你可以选择 $y$ 进制下的数 $x$ 的某**一个**有效位上数值增加 $1$。 第一个非零数位及其后面的数位是有效位。 注意: * **对于每次操作**,你可以任意取 $y\in[2,+\infty)$; * 你需保证增加操作不会使 $y$ 进制下的数 $x$ 产生进位。 现在你需要求 $n$ 次操作后这个数最大是多少。 答案以十进制输出,并对 $10^9+7$ 取模。你需要输出的是这个数的最大值对 $10^9+7$ 取模的结果,而并非对 $10^9+7$ 取模后的最大值。 ## Input **本题有多组测试数据。** 第一行一个整数 $T$,表示数据组数。 接下来 $T$ 行,每行两个整数 $x,n$,分别表示初始数字、操作次数。 ## Output 对于每组测试数据,输出一行一个整数,表示 $x$ 进行 $n$ 次操作后的最大值。 [samples] ## Note **【样例解释】** 很明显,$2$ 在二进制时为 $10$,在三或更高进制时为 $2$。 二进制时,在第一位 $+1$ 会导致二进制产生进位,只能在第二位 $+1$,此时得到的结果为 $11$,转换为十进制为 $3$。 在三或更高进制时,只能往末位 $+1$,三进制下会产生进位,舍去。四或更高进制时得到结果均为 $3$,转化为十进制的结果也是 $3$。 **【数据范围】** **本题采用捆绑测试。** - Subtask #1($20\text{ pts}$):$x\le 2$。 - Subtask #2($20\text{ pts}$):$n=1$。 - Subtask #3($60\text{ pts}$):无特殊限制。 对于 $100\%$ 的数据,$1\le x,n\le10^9$,$1\le T\le10^6$。
Samples
Input #1
1
2 1
Output #1
3
API Response (JSON)
{
  "problem": {
    "name": "「CZOI-R1」进制",
    "description": {
      "content": "你有一个数 $x$,你需要对它进行 $n$ 次操作。 每次操作,你可以选择 $y$ 进制下的数 $x$ 的某**一个**有效位上数值增加 $1$。   第一个非零数位及其后面的数位是有效位。 注意: * **对于每次操作**,你可以任意取 $y\\in[2,+\\infty)$; * 你需保证增加操作不会使 $y$ 进制下的数 $x$ 产生进位。 现在你需要求 $n$ 次操作后这个数最大是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10797"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一个数 $x$,你需要对它进行 $n$ 次操作。\n\n每次操作,你可以选择 $y$ 进制下的数 $x$ 的某**一个**有效位上数值增加 $1$。  \n第一个非零数位及其后面的数位是有效位。\n\n注意:\n* **对于每次操作**,你可以任意取 $y\\in[2,+\\infty)$;\n* 你需保证增加操作不会使 $y$ 进制下的数 $x$ 产生进位。\n\n现在你需要求 $n$ 次操作后这个数最大是多少。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments