线上OJ:
一本通:1937:【06NOIP普及组】数列 (opens in a new tab)
AcWing:428. 数列 (opens in a new tab)
洛谷:P1062 [NOIP2006 普及组] 数列 (opens in a new tab)
思考:
这道题大概率是一道可以使用“瞪眼法”找到规律的题目。我们尝试把数据补充的更多,以便于寻找规律 当 k=3 时,k的幂次为1, 3, 9, 27, 81......

从上述推理中,我们发现要输出的幂次和中的第 N 项(也就是幂次和中的序号N),对应的二进制位数和幂次和对应的二进制位数相同。
举例:
N=7时,7 的二进制是 ,即第0位,第1位,第2位均为1, 。转成 k 进制(k=3)时的幂次和为 , (即第0位,第1位,第2位均为1)
N=5时,5 的二进制是 ,即第0位,第2位均为1,转成 k 进制(k=3)时 (即第0位,第2位均为1)
N=12时,12的二进制是 ,即第2位,第3位均为1,转成 k 进制(k=3)时 (即第2位,第3位均为1)
结论:这道题就变成了先把 N 转成二进制,然后再转成 k 进制输出即可
题解代码:
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
int main()
{
cin >> k >> n;
int a[15], i; // i 定义在外面,后续可以直接用。因为N小于1000。且1024位2的10次方,所以a[11]足以表示1000以内的二进制数
// 把十进制n转成二进制
for(i = 0; n > 0; i++) a[i] = n%2, n/=2; // 用除2取余法,保留余数至a[i],然后n/2准备下一轮除余。注:a[0]是最低位
for(int j = i - 1; j >= 0; j--) // 按k为基数,倒序计算新的数值
ans = ans * k + a[j];
cout << ans << endl; //
return 0;
}
/*
1 3 9 27 81
1 3 4 9 10 12 13 27 28 30 31 36 37 39 40
0 1 01 2 02 12 012 3 03 13 013 23 023 123 0123
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 = 2^2 + 2^1 + 2^0 111
13 = 3^2 + 3^1 + 3^0
*/