利用题目中给出的公式和hint可以得到两个有用的公式：
phi^(n) = phi^(n-1)+phi^(n-2)
2*(phi^n) = phi^(n+1)+phi^(n-2)
可以计算出phi^100远大于10^9，所以推测最后得到的phi进制的数整数和小数部分应该不会超过100位，事实表明，50位就能过。
所以最终变成了简单的模拟。
Golden Radio Base
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 363 Accepted Submission(s): 165
phi-nary.
Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard
form, using the algebraic properties of the base φ — most notably that φ + 1 = φ 2 . For instance, 11(φ) = 100(φ). Despite using an irrational number base, when using standard form, all on-negative integers have a unique representation as a terminating
(finite) base-φ expansion. The set of numbers which possess a finite base-φ representation is the ring Z[1 + √5/2]; it plays the same role in this numeral systems as dyadic rationals play in binary numbers, providing a possibility to multiply.
Other numbers have standard representations in base-φ, with rational numbers having recurring representations. These representations are unique, except that numbers (mentioned above) with a terminating expansion also have a non-terminating expansion, as they
do in base-10; for example, 1=0.99999….
Coach MMM, an Computer Science Professor who is also addicted to Mathematics, is extremely interested in GRB and now ask you for help to write a converter which, given an integer N in base-10, outputs its corresponding form in base-φ.
1 2 3 6 10
1 10.01 100.01 1010.0001 10100.0101Hint
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int base=100;
int n;
int wei[220];
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(wei,0,sizeof(wei));
wei[base]=n;
while(true)
{
bool flag=false;
for(int i=0;i<200;i++)
{
if(wei[i]>1)
{
int t=wei[i];
wei[i]=t%2;
wei[i+1]+=t/2;
wei[i-2]+=t/2;
flag=true;
}
}
for(int i=0;i<200;i++)
{
if(wei[i]&&wei[i+1])
{
int t=min(wei[i],wei[i+1]);
wei[i]-=t; wei[i+1]-=t;
wei[i+2]+=t;
flag=true;
}
}
if(flag==false) break;
}
int st=-1,ed=-1;
for(int i=0;i<202;i++)
if(wei[i]) { st=i; break; }
for(int i=202;i>=0;i--)
if(wei[i]) { ed=i; break; }
for(int i=ed;i>=st;i--)
{
printf("%d",wei[i]);
if(i==base&&st!=i) putchar('.');
}
putchar(10);
}
return 0;
}