♐ CSP_J 组真题
2006年
4. 数列

线上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 的二进制是 (111)2(111)_2,即第0位,第1位,第2位均为1, 7=22+21+207 = 2^2 + 2^1 + 2^0。转成 k 进制(k=3)时的幂次和为 32+31+30=133^2 + 3^1 + 3^0 = 13(111)3=13(111)_3=13(即第0位,第1位,第2位均为1)
N=5时,5 的二进制是 (101)2(101)_2,即第0位,第2位均为1,转成 k 进制(k=3)时 (101)3=10(101)_3=10(即第0位,第2位均为1)
N=12时,12的二进制是 (1100)2(1100)_2,即第2位,第3位均为1,转成 k 进制(k=3)时 (1100)3=36(1100)_3=36(即第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
*/