考察:找规律(?)
发现规律后代码超短..我还想复杂了...
思路:
第1项是k0 第2项是k1 第3项是k0+k1 可以发现指数和第n项的二进制排列相同..通过这个制造映射,求出答案
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 using namespace std; 5 typedef long long LL; 6 int qsm(int a,int k) 7 { 8 int res = 1; 9 while(k) 10 { 11 if(k&1) res = res*a; 12 a = a*a; 13 k>>=1; 14 } 15 return res; 16 } 17 int main() 18 { 19 int k,n; 20 scanf("%d%d",&k,&n); 21 int res = 0,i = 0; 22 while(n) 23 { 24 int t = n%2; 25 if(t) res+=qsm(k,i); 26 n/=2; 27 i++; 28 } 29 printf("%d\n",res); 30 return 0; 31 }