题解 P1062 【数列】

· · 题解

看了一遍题解，发现大家都觉得这是个进制转换题

新的思路：

其实吧，这题有个特点，长得跟快速幂很像

把样例的数列转换成三进制:

序号 1 2 3 4 5 6 7
三进制 1 10 11 100 101 110 111
十进制 1 3 4 9 10 12 13

注意三进制的数字，为什么给人一种二进制的感觉?

（楼上有dalao说这就是二进制）

把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列

这就是说，每一个k的方幂只能有或者没有

有为0，没有为1

如果第i位是1，那么答案要加上k^i

跟快速幂的思想很像

快速幂模板

所以我就写出一个跟快速幂差别很小的东西：

#include<cstdio>
int k,n;
long long ans,base=1;
int main(){
    scanf("%d%d",&k,&n);
    /**********************************/
    while(n){
        if(n&1)ans+=base;//跟快速幂只有这里不一样
        base*=k;
        n>>=1;
    }
    /**********************************/
    printf("%d",ans);
    return 0;
}

（按理说这个应该跑得比用pow的大佬们快）（按理说

这道题不仅可以考验进制转换

还可以练习快速幂！