企业官网建设流程全解析

好好好数

时间限制：1 秒
空间限制：256 MB

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

在上周的周赛 Round 57 中，双好数的构造题非常有趣。于是，在这周的周赛中，好数又回来了！但其实这两题并没有什么关系，还是重新看看题吧！

小苯有一个数字n nn，他定义k kk-好数为：可以表示为若干个不同的k kk的整数次幂之和的数字。

例如：30 = 3 3 + 3 1 30 = 3^3 + 3^130=33+31，因此30 3030是一个3 33-好数；而2 22不是一个3 33-好数（虽然有：2 = 3 0 + 3 0 2 = 3^0 + 3^02=30+30，但好数要求次幂数字不同）。

小苯有一个整数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 + 3060=30+30，因此可以分解为两个3 33-好数，可以证明不存在更优的分解方式。

数据范围与提示

• 1 ≤ T ≤ 10 4 1 \le T \le 10^41≤T≤104
• 1 ≤ n , k ≤ 10 18 1 \le n, k \le 10^{18}1≤n,k≤1018
• k 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_{i=0}^{m} d_i \cdot k^in=∑i=0m​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 = 1k=1

• 当k = 1 k=1k=1时，1 11的任意次幂都是1 11。一个1 11-好数可以表示为任意多个不同的1 11的幂次之和，因此任意正整数都是1 11-好数。
• 所以n nn本身就是一个1 11-好数，答案为1 11。

3. 算法实现

1. 读入T TT组数据。
2. 对于每组( n , k ) (n, k)(n,k)：
   • 若k = 1 k = 1k=1，直接输出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 k=2k=2时）。总复杂度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 k=1k=1输出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。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n;ll k;voidSolve(){cin>>n>>k;if(k==1){cout<<"1\n";return;}ll res=0;while(n){res=max(res,n%k);n/=k;}cout<<res<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cin>>T;while(T--)Solve();return0;}