【RQNOJ】PID4 / 数列

题目描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：

1，3，4，9，10，12，13，…

（该序列实际上就是：3^0，3^1，3^0+3^1，3^2，3^0+3^2，3^1+3^2，

3^0+3^1+3^2，…）

请你求出这个序列的第N项的值（用10进制数表示）。

分析：
对于任意阶n， 由k的n阶（小于n阶）次幂组成的序列为：
0*k^n + 0*k^(n-1)+...+1*k^0 ,  0*k^n + 0*k^(n-1) + ...+ 1*k^1 + 0* k^0 , ..., 1*k^n + 1*k^(n-1) + ... + 1* k^0

上面是一个二项式的完全表达式， 对于n，每个项由(n+1)个系数项组成：bit表示为[b0...1, b1...1], 共2^(n+1) -1 项
对于序列的第N项，如果N表示为（p1*2^0 + p2*2^1+ ...pt*2^(t-1) )
那么序列的第N项的值表示为 p1*k^0 + p2*k^1 + ... pt*k^(t-1)

实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


unsigned long seriesN (unsigned int key, unsigned int N)
{
    unsigned long sc = 1;
    unsigned long ret = 0;

    while (N > 0)
    {
        ret += (N & 0x01) > 0 ? sc : 0;
        sc *= key;
        N = N >> 1
    }

    return ret;
}