好好好数时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述在上周的周赛 Round 57 中双好数的构造题非常有趣。于是在这周的周赛中好数又回来了但其实这两题并没有什么关系还是重新看看题吧小苯有一个数字n nn他定义k kk-好数为可以表示为若干个不同的k kk的整数次幂之和的数字。例如30 3 3 3 1 30 3^3 3^1303331因此30 3030是一个3 33-好数而2 22不是一个3 33-好数虽然有2 3 0 3 0 2 3^0 3^023030但好数要求次幂数字不同。小苯有一个整数n nn他想知道n nn最少可以被表示成几个k kk-好数的和请你帮帮他吧。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 10 4 ) T\ (1 \le T \le 10^4)T(1≤T≤104)代表数据组数。每组测试数据描述如下在一行上输入两个整数n , k ( 1 ≤ n ≤ 10 18 , 1 ≤ k ≤ 10 18 ) n, k\ (1 \le n \le 10^{18},\ 1 \le k \le 10^{18})n,k(1≤n≤1018,1≤k≤1018)表示小苯的数字n nn、k kk-好数的k kk。输出描述在一行上输出一个整数代表最少可以将n nn分解成k kk-好数的个数。示例示例 1输入2 60 3 114 514输出2 114说明对于第一组测试数据30 3030是3 33-好数而60 30 30 60 30 30603030因此可以分解为两个3 33-好数可以证明不存在更优的分解方式。数据范围与提示1 ≤ T ≤ 10 4 1 \le T \le 10^41≤T≤1041 ≤ n , k ≤ 10 18 1 \le n, k \le 10^{18}1≤n,k≤1018k kk-好数要求分解为不同的k kk的整数次幂之和。本题核心在于分析一个数按k kk进制展开后每一位上的数字代表需要多少个对应次幂由于同一k kk-好数中同一幂次只能出现一次因此需要合理分组计数。解题思路本题是进制展开与贪心分组的数学题。定义k kk-好数为若干个不同的k kk的整数次幂之和。要求将给定的n nn最少分解为几个k kk-好数之和。1. 问题等价转化将n nn表示为k kk进制数即n ∑ i 0 m d i ⋅ k i n \sum_{i0}^{m} d_i \cdot k^in∑i0m​di​⋅ki其中0 ≤ d i k 0 \le d_i k0≤di​k。一个k kk-好数在k kk进制下每一位只能是0 00或1 11因为每个k kk的幂次最多使用一次。若将n nn拆分成若干个k kk-好数之和相当于在k kk进制的每一位上将数字d i d_idi​拆分成d i d_idi​个1 11并分配到不同的k kk-好数中。每个k kk-好数在每一位最多贡献一个1 11因此为了覆盖所有位上的d i d_idi​个1 11至少需要max ⁡ i d i \max_i d_imaxi​di​个k kk-好数。同时我们可以构造恰好max ⁡ i d i \max_i d_imaxi​di​个k kk-好数对于每一位i ii将d i d_idi​个1 11分配给前d i d_idi​个k kk-好数即可每个k kk-好数在该位取1 11或0 00。因此最少个数就是max ⁡ i d i \max_i d_imaxi​di​。2. 特殊情况k 1 k 1k1当k 1 k1k1时1 11的任意次幂都是1 11。一个1 11-好数可以表示为任意多个不同的1 11的幂次之和因此任意正整数都是1 11-好数。所以n nn本身就是一个1 11-好数答案为1 11。3. 算法实现读入T TT组数据。对于每组( n , k ) (n, k)(n,k)若k 1 k 1k1直接输出1。否则循环执行计算n % k记录当前余数更新答案res max(res, n % k)n / k。当n变为0 00时结束输出res。4. 复杂度分析时间复杂度每组数据需要对n nn进行k kk进制展开循环次数为O ( log ⁡ k n ) O(\log_k n)O(logk​n)最坏约为60 6060次当k 2 k2k2时。总复杂度O ( T log ⁡ n ) O(T \log n)O(Tlogn)T ≤ 10 4 T \le 10^4T≤104完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用常数个变量。总结将n nn写成k kk进制后每一位的数字代表该幂次需要出现的次数。由于每个k kk-好数在同一位最多贡献一次最少需要的k kk-好数个数就是所有位数字的最大值。特判k 1 k1k1输出1 11。代码简要说明主函数读入T TT循环处理每组数据。对于每组( n , k ) (n, k)(n,k)若k 1输出1并继续。初始化res 0当n 0时res max(res, n % k)n / k。输出res。使用long long存储n , k n, kn,k因为范围可达10 18 10^{18}1018。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll k;voidSolve(){cinnk;if(k1){cout1\n;return;}ll res0;while(n){resmax(res,n%k);n/k;}coutres\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cinT;while(T--)Solve();return0;}