题解：P1062 [NOIP2006 普及组] 数列

· · 题解

题解：P1062 [NOIP2006 普及组] 数列

注意到 n 的二进制和答案的 k 进制有某种关联：（以下表格中 k=3）

n（十进制） n（二进制） 答案（k=3 进制） 答案（十进制）
1 1 1 1
2 10 10 3
3 11 11 4
4 100 100 9
5 101 101 10
6 110 110 12
7 111 111 13
8 1000 1000 27

因此 n 的二进制表示和答案的 k 进制表示相同。

可得代码：

#include <bits/stdc++.h>
using namespace std;
long long n, k, c = 1, ans;
// c 表示当前位的底数（k 的 [这是第几位] 次方）
int main()
{
    cin >> k >> n;
    while (n)
    {
        ans += c * (n & 1); // 如果当前 n 的最后一位是 1，则将 ans 加上 c
        c *= k;
        n >>= 1; // 将 n 的二进制的最后一位去除
    }
    cout << ans;
}