codeforces 305B. Continued Fractions （递归的思想）

​​http://codeforces.com/problemset/problem/305/B​​

大致题意：问

是否等于

开始直接用浮点递归处理。。。结果可想而知。

再一次出现运行结果不一样的问题：

对于数据：

39088169 2415781736 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

39088169 24157817

36

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

YES

结果在codeforces测评机上的结果是：

可能真和机器相关。

浮点问题横亘在前方。。。这个方案作罢。

其实我们知道它一定和递归有点关系，继续探索发现。。。

我们看一个简单的等式：

把它上下翻转一下呢？

是的，等号右边新的分数，等号左边的加式都和原来有一定的相似度，递归就这样形成了

这样迭代下去，如果是相等的，那么右边一定是等于0的

写的时候注意这样的陷阱：

跳出语句不要这样写：

if(q==0||a[i]*q<0||a[i]*q>p) break;

105000000000078855*105000000000078855=262882295792523313

是的，我亲测了。

cin>>p;

cout<<p*p<<endl;

105000000000078855

262882295792523313

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
LL a[100],p,q,n;
int main()
{
    //freopen("cin.txt","r",stdin);
    while(cin>>p>>q){
        scanf("%I64d",&n);
        for(int i=0;i<n;i++){
            scanf("%I64d",&a[i]);
        }
        int i=0;
        for(i=0;i<n;i++){
            if(q==0||p/q<a[i]) break;
            p=p-a[i]*q;
            LL t=p;
            p=q;
            q=t;
        }
        if(i==n&&q==0) puts("YES");
        else puts("NO");
    }
    return 0;
}