P1062 数列

· · 个人记录

P1062 数列

我们把题目中的栗子搞出来：

\left.\begin{array}{}&i&1&3&4&9&10&12&13\\&\text{拆分}& 3^0&3^1&3^0+3^1&3^2&3^0+3^2&3^1+3^2&3^0+3^1+3^2&\\&\text{三进制}&001&010&011&100&101&110&111&\end{array}\right.

看最后一列，好像是二进制啊？？？

我们把最后一列当成二进制，再转换成十进制：

\left.\begin{array}{}&\text{二进制}&001&010&011&100&101&110&111&\\&\text{十进制}&1&2&3&4&5&6&7&\end{array}\right.

嘿！有趣！

所以我们只要把上面这个过程反过来就好了！

也就是：对于N，先转换成二进制，再当成k进制转换成十进制。

不得不说这个过程有点像快速幂。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k;
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
long long solve(int n,int k){
    long long x=1,s=0;
    while(n){
        if(n&1)s+=x;
        x*=k;
        n>>=1;
    }
    return s;
}
int main(){
    k=read();n=read();
    printf("%lld\n",solve(n,k));
    return 0;
}