斐波那契真的牛掰

题目链接

题目描述：

小Y在研究数字的时候，发现了一个神奇的等式方程 ，他屈指算了一下有很多正整数x满足这个等式，比如1和2，现在问题来了，他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。
(表示按位异或运算)

输入描述:

第一行是一个正整数 T<=100，表示查询次数。
接着有T行，每行有一个正整数N(N<=1e12)，表示小Y的查询。
输出描述:：
对于每一个查询N，输出第N个满足题中等式的正整数，并换行。
示例1

输入：

4
1
2
3
10

输出：

1
2
4
18

打表列出前100个数，找下规律

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; using namespace std; string solve(int n){ //将十进制转换成二进制 string s;char c;while(n){c = '0' + n % 2;s = c + s;n /= 2;}return s; } int main (){ int now=0; printf("查询次数 答案 二进制形式\n"); for(int i=1;;i++){if(((i ^ (2 * i)) == 3 * i)){string s;int n;s = solve(i);printf("%4d%6d ",++now,i);cout << s << endl;} if(now == 100)break;} return 0; } 查询次数 答案 二进制形式1 1 1 //二进制1位的有1个 2 2 10 //二进制2位的有1个 3 4 100 4 5 101 //二进制3位的有2个5 8 10006 9 10017 10 1010 //二进制4位的有3个8 16 100009 17 1000110 18 1001011 20 1010012 21 10101 //二进制5位的有5个13 32 100000 14 33 10000115 34 10001016 36 10010017 37 10010118 40 10100019 41 10100120 42 101010 //二进制6位的有8个21 64 1000000 22 65 100000123 66 100001024 68 100010025 69 100010126 72 100100027 73 100100128 74 100101029 80 101000030 81 101000131 82 101001032 84 101010033 85 1010101 //二进制7位的有13个34 128 1000000035 129 1000000136 130 1000001037 132 1000010038 133 1000010139 136 1000100040 137 1000100141 138 1000101042 144 1001000043 145 1001000144 146 1001001045 148 1001010046 149 1001010147 160 1010000048 161 1010000149 162 1010001050 164 1010010051 165 1010010152 168 1010100053 169 1010100154 170 1010101055 256 10000000056 257 10000000157 258 10000001058 260 10000010059 261 10000010160 264 10000100061 265 10000100162 266 10000101063 272 10001000064 273 10001000165 274 10001001066 276 10001010067 277 10001010168 288 10010000069 289 10010000170 290 10010001071 292 10010010072 293 10010010173 296 10010100074 297 10010100175 298 10010101076 320 10100000077 321 10100000178 322 10100001079 324 10100010080 325 10100010181 328 10100100082 329 10100100183 330 10100101084 336 10101000085 337 10101000186 338 10101001087 340 10101010088 341 10101010189 512 100000000090 513 100000000191 514 100000001092 516 100000010093 517 100000010194 520 100000100095 521 100000100196 522 100000101097 528 100001000098 529 100001000199 530 1000010010100 532 1000010100

找规律：

答案对应的二进制的位数符合斐波那契数，（打表斐波那契）

N和斐波那契的和有关，给定一个N可以判断，此时答案的二进制位数。（打表斐波那契的和）

举一个例子：当N等于70，答案的二进制为：100100010，根据打表的斐波那契的和，可以判断答案的二进制是9位（55对应1000000000），余下的100010，刚好是N-55的二进制。递推！

代码实现：

#include<bits/stdc++.h> #define ll long long #define N 100005 int inf = 0x3f3f3f3f; ll f[N],sum[N],ans[N]; using namespace std; int main (){ f[1] = f[2] = 1;sum[1] = 1; sum[2] = 2;for(int i = 3; i <= 60; i++){ //打表斐波那契、斐波那契的和 f[i] = f[i-1] + f[i-2];sum[i] = sum[i-1] + f[i]; }int t;cin>>t;while(t--){ll n;cin>>n;ll ans=0;while(n){for(int i = 1; i <= 60; i ++){if(n <= sum[i] && n > sum[i-1]){ //找到n对应答案的二进制位数 ans += 1LL << i-1;n -= sum[i-1] + 1LL;//ans += (ll) pow(2, i-1LL);//pow前面要加longlong要不然会爆数据 break;}} }cout<<ans<<endl; }return 0; } 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 F- 1 + 2 = 3? (好难的找规律题)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。