【数列计算】题解

题干信息解读
问题描述：给定正整数 n（3≤n≤15），构造一个递增序列，序列元素包括n的所有乘方幂（如 n⁰, n¹, n²...）以及这些乘方幂中有限个互不相等的和（如 n⁰+n¹, n⁰+n² 等）。要求求出该序列的第 K 项（10 进制）。
核心规律：序列的第K项可通过K的二进制表示推导 —— 二进制中第 i 位（从 0 开始）为 1 时，累加 nⁱ ，总和即为第 K 项。

整体做题思路
规律分析：
观察序列构造可知，序列元素与K的二进制表示存在对应关系：
二进制数的每一位对应是否包含n的某次方（第i位为 1 则包含nⁱ）。
例如：K=3（二进制11）对应n⁰ + n¹，K=4（二进制100）对应n²。
算法步骤：
1.将K转换为二进制数。
2.遍历二进制的每一位，若第 i 位为 1，则累加 nⁱ 。
3.累加结果即为序列的第 K 项。
实现技巧：
1.无需显式转换二进制，通过位运算（K & 1判断最低位，K >>= 1右移）逐位处理。
2.动态计算 nⁱ （初始为n⁰=1，每次循环乘以 n 得到下一次方），避免重复计算。

难点和注意事项
二进制位对应关系：
二进制的第i位（从 0 开始，最低位为第 0 位）对应 nⁱ ，需注意位序与指数的对应，避免错位。
数据范围处理：
K 最大为 1000，二进制最多 10 位（2¹⁰=1024），因此 n 的最高次方为 n⁹ 。
n最大 15，15⁹ 约 5.76e10，用long long可容纳，避免整数溢出。
位运算细节：
循环终止条件为K > 0，确保所有位都被处理；每次处理后 K 右移一位，同时更新 n 的次方值。

AC代码（如有雷同，纯属巧合）

#include <iostream>
using namespace std;

int main() {
    int n, K;
    cin >> n >> K;
    
    long long result = 0;  // 存储第K项结果
    long long power = 1;   // 存储n^i，初始为n^0=1
    
    // 遍历K的二进制每一位
    while (K > 0) {
        // 若当前最低位为1，则累加n^i
        if (K & 1) {
            result += power;
        }
        K >>= 1;       // K右移一位，处理下一位
        power *= n;    // 更新为n的下一次方（i+1次方）
    }
    
    cout << result << endl;
    return 0;
}

时间与空间复杂度
时间复杂度：O(log K)
循环次数为K的二进制位数，K最大 1000 时二进制有 10 位，因此最多循环 10 次。
空间复杂度：O(1)
仅使用固定变量（result、power等），空间消耗与输入规模无关。