十分精妙的一道题，斐波那契数列和黄金比例\(\Phi\)的内在有着奇妙的联系。
我们设\(x=\frac{\sqrt{5}+1}{2}\)，则根据题目给出的规律，有\(x^2=x+1\)。
下面我们通过列举，试图找出规律：
- \(x^0=1\)
- \(x^1=x\)
- \(x^2=x+1\)
- \(x^3=2x+1\)
- \(x^4=3x+2\)
- \(x^5=5x+3\)
- \(x^6=8x+5\)
\(…\)
没错，\(x\)的系数构成了一个斐波那契数列\(\{1,0,1,1,2,3,5,8,…\}\)，而容易发现\(x^k=x^{k-1}+x^{k-2}\)。所以我们把\(A,B\)序列不断降次，直到只剩若干\(x^0\)和\(x^1\)，然后计算具体值判断即可。
这里把\(A,B\)相减得到\(C\)，最后看结果的正负性，效果是一样的。
需要注意的是，降次过程中可能会出现超long long的情况，怎么解决呢？我们发现\(x^k\)的系数如果超过某个限制，以至于\(1\sim (k-1)\)即使全是负数，结果也减不到负数。所以在执行途中加一个判断如果\(x^k\)的绝对值大于某个数，就直接输出。这里使用\(10^5\)过了，但为了保险还是大点好。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
string a,b;
long long c[100010];
int main(){
cin>>a>>b;
int len=max(a.size(),b.size());
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
a.resize(len,'0'),b.resize(len,'0');
a=' '+a,b=' '+b;
for(int i=1;i<=len;i++) c[i]=a[i]-b[i];
for(int i=len;i>=3;i--){
if(llabs(c[i])>100000){
if(c[i]>0) cout<<'>';
else cout<<'<';
return 0;
}
c[i-1]+=c[i],c[i-2]+=c[i];
}
if(c[1]==c[2]&&c[1]==0){
cout<<'=';
return 0;
}
double x=(sqrt(5)+1)/2;
double aa=1.0*c[2]*x+1.0*c[1];
if(aa>0) cout<<'>';
else cout<<'<';
return 0;
}