当前位置：首页 > news >正文

打卡信奥刷题（3293）用C++实现信奥题 P9002 [RC-07] 心跳

news 2026/5/22 23:20:58

P9002 [RC-07] 心跳

题目描述

对正整数xxx，设f(x,B)f(x,B)f(x,B)表示xxx在BBB进制下的数位和。说一个正整数ppp是BBB-好的，当且仅当对于任意正整数q<pq<pq<p都有f(p,B)≥f(q,B)f(p,B)\ge f(q,B)f(p,B)≥f(q,B)。

给定正整数nnn和BBB，计算有多少个≤n\le n≤n的正整数是BBB-好的。

输入格式

本题单个测试点内有多组数据。

第一行是数据组数TTT。

接下来TTT行，每行两个正整数n,Bn,Bn,B。

输出格式

输出TTT行，每行一个非负整数，为答案。

输入输出样例 #1

输入 #1

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

输出 #1

3 6 49 60 28238934 760

说明/提示

样例解释

这里只解释第二组询问的输出。三进制下，1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9的数位和分别为1,2,1,2,3,2,3,4,11,2,1,2,3,2,3,4,11,2,1,2,3,2,3,4,1，据此容易看出只有1,2,4,5,7,81,2,4,5,7,81,2,4,5,7,8是333-好的，所以输出666。

数据范围

所有数据均满足：1≤T≤1051\le T\le 10^51≤T≤105，1≤n≤10181\le n\le 10^{18}1≤n≤1018，2≤B≤10182\le B\le 10^{18}2≤B≤1018。

子任务111（505050分）：T≤104T\le 10^4T≤104，n,B≤100n,B\le 100n,B≤100。
子任务222（303030分）：B=2B=2B=2。
子任务333（202020分）：无特殊限制。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintN=65;intT;LL n,B,now,ans,num[N];inlinevoidsolve(){scanf("%lld%lld",&n,&B);now=0;while(n)num[++now]=n%B,n/=B;ans=(B-1)*now*(now-1)/2+(num[now]-1)*now;for(inti=now-1;i>=1;i--){if(num[i]==B-1)ans+=(i==1)+1;elseif(num[i]==B-2){boolflag=true;for(intj=i-1;j>=1;j--)if(num[j]!=B-1){flag=false;break;}if(flag)ans++;break;}elsebreak;}printf("%lld\n",ans+(now==1));}intmain(){scanf("%d",&T);while(T--)solve();return0;}