{"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$ 行，每行两个正整数 $n,B$。\n\n## Output\n\n输出 $T$ 行，每行一个非负整数，为答案。\n\n[samples]\n\n## Note\n\n**样例解释**\n\n这里只解释第二组询问的输出。三进制下，$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$。\n\n**数据范围**\n\n所有数据均满足：$1\\le T\\le 10^5$，$1\\le n\\le 10^{18}$，$2\\le B\\le 10^{18}$。\n\n- 子任务 $1$（$50$ 分）：$T\\le 10^4$，$n,B\\le 100$。\n- 子任务 $2$（$30$ 分）：$B=2$。\n- 子任务 $3$（$20$ 分）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9002","tags":["O2优化","数位 DP","进制"],"sample_group":[["6\n4 2\n9 3\n1000 2\n1000 20\n28238934 154154154154154\n23389348458425 5","3\n6\n49\n60\n28238934\n760"]],"created_at":"2026-03-03 11:09:25"}}