AcWing 428. 数列

原题链接

考察:找规律(?)

发现规律后代码超短..我还想复杂了...

思路:

        第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 }

 

上一篇:18. 4Sum[M]四数之和


下一篇:[HEOI2016/TJOI2016]序列(CDQ分治优化DP)