[RC-07] 心跳

Luogu

IDLGP9002

Time1000ms

Memory512MB

DifficultyP4

O2优化数位 DP进制

对正整数 $x$，设 $f(x,B)$ 表示 $x$ 在 $B$ 进制下的数位和。说一个正整数 $p$ 是 $B$-好的，当且仅当对于任意正整数 $q<p$ 都有 $f(p,B)\ge f(q,B)$。给定正整数 $n$ 和 $B$，计算有多少个 $\le n$ 的正整数是 $B$-好的。 ## Input 本题单个测试点内有多组数据。第一行是数据组数 $T$。接下来 $T$ 行，每行两个正整数 $n,B$。 ## Output 输出 $T$ 行，每行一个非负整数，为答案。 [samples] ## Note **样例解释** 这里只解释第二组询问的输出。三进制下，$1,2,3,4,5,6,7,8,9$ 的数位和分别为 $1,2,1,2,3,2,3,4,1$，据此容易看出只有 $1,2,4,5,7,8$ 是 $3$-好的，所以输出 $6$。 **数据范围** 所有数据均满足：$1\le T\le 10^5$，$1\le n\le 10^{18}$，$2\le B\le 10^{18}$。 - 子任务 $1$（$50$ 分）：$T\le 10^4$，$n,B\le 100$。 - 子任务 $2$（$30$ 分）：$B=2$。 - 子任务 $3$（$20$ 分）：无特殊限制。

Samples

Input #1

6
4 2
9 3
1000 2
1000 20
28238934 154154154154154
23389348458425 5

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[RC-07] 心跳",
    "description": {
      "content": "对正整数 $x$，设 $f(x,B)$ 表示 $x$ 在 $B$ 进制下的数位和。说一个正整数 $p$ 是 $B$-好的，当且仅当对于任意正整数 $q<p$ 都有 $f(p,B)\\ge f(q,B)$。 给定正整数 $n$ 和 $B$，计算有多少个 $\\le n$ 的正整数是 $B$-好的。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9002"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对正整数 $x$，设 $f(x,B)$ 表示 $x$ 在 $B$ 进制下的数位和。说一个正整数 $p$ 是 $B$-好的，当且仅当对于任意正整数 $q<p$ 都有 $f(p,B)\\ge f(q,B)$。\n\n给定正整数 $n$ 和 $B$，计算有多少个 $\\le n$ 的正整数是 $B$-好的。\n\n## Input\n\n本题单个测试点内有多组数据。\n\n第一行是数据组数 $T$。\n\n接下来 $T$ 行，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments