题意：
给出一个正整数\(n(1 \leq n \leq 10^9)\)，要你把它转换成\(\phi\)进制，其中\(\phi = \frac{1+\sqrt{5}}{2}\)。
转换的规则还有如下限制：- 每一位只有\(0\)或者\(1\)
- 不能有相邻的两个\(1\)出现
- 输出没有多余的\(0\)
分析：
这题看起来很吓人，要把一个十进制整数转化成一个无理数进制的形式。
但是只要根据题目的提示，抓住两个要点就能在\(\phi\)进制下作加法：- 根据\(2\phi^2=\phi^3+1\)，我们得到在\(\phi\)进制的等式：\(100(\phi)+100(\phi)=1001(\phi)\)。有了这个我们就可以计算\(1+1\)，更进一步就能计算任何正整数。
- 根据\(\phi+1=\phi^2\)，有\(11(\phi)=100(\phi)\)，我们就可以将连续的两个\(1\)进位。
所以这题就是根据这两条规则，模拟\(\phi\)进制下的加法。
因为\(n\)比较大，所以可以预处理\(\phi\)进制下的\(2^x\)这样的数，然后将\(n\)二进制展开。#include#include #include using namespace std;const int maxl = 150;const int off = 50;int p[30][maxl], ans[maxl];bool findadd(int* a) { for(int i = 0; i < maxl; i++) if(a[i] >= 2) return true; return false;}bool find11(int* a) { for(int i = 0; i + 1 < maxl; i++) if(a[i] == 1 && a[i+1] == 1) return true; return false;}void add(int* a, int* b, int* c) { for(int i = 0; i < maxl; i++) c[i] = a[i] + b[i]; for(;;) { if(findadd(c)) { for(int i = 0; i < maxl; i++) if(c[i] >= 2) { int t = c[i] >> 1; c[i] = c[i] & 1; c[i-1] += t; c[i+2] += t; } } if(find11(c)) { for(int i = 0; i + 1 < maxl; i++) if(c[i] == 1 && c[i+1] == 1) { c[i] = c[i+1] = 0; c[i-1]++; } } if(!findadd(c) && !find11(c)) break; }}void preprocess() { p[0][off] = 1; for(int i = 1; (1 << i) <= 1000000000; i++) add(p[i-1], p[i-1], p[i]);}void solve(int n) { int cnt = 0; while(n) { if(n & 1) add(ans, p[cnt], ans); n >>= 1; cnt++; }}void print(int* a) { int s, t; for(int i = 0; i < maxl; i++) if(a[i]) { s = i; break; } for(int i = maxl-1; i >= 0; i--) if(a[i]) { t = i; break; } for(int i = s; i <= off; i++) printf("%d", a[i]); if(t > off) { printf("."); for(int i = off + 1; i <= t; i++) printf("%d", a[i]); } printf("\n");}int main() { preprocess(); int n; while(scanf("%d", &n) == 1) { memset(ans, 0, sizeof(ans)); solve(n); print(ans); } return 0;}