codeforces Round #184 Div.2 B Continued Fractions

一开始直接用递归求后一个分数式的值，每求一步约分一次，过了小数据，大数据没过……后来发现是因为中间两个long long相乘溢出了……

看了别人的代码才明白，只要思维稍微转化一下，这题就能变得很简单……

 1 #include <cstring>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define LL long long int
 9 
10 const int MAXN = 100;
11 
12 int n;
13 LL p, q, a[MAXN];
14 
15 int main()
16 {
17     //freopen("in.txt", "r", stdin );
18     //freopen("out.txt", "w", stdout );
19     while ( ~scanf( "%I64d%I64d", &p, &q ) )
20     {
21         int i;
22         scanf( "%d", &n );
23         for ( i = 0; i < n; ++i )
24             scanf( "%I64d", &a[i] );
25 
26         for ( i = 0; i < n; ++i )
27         {
28             if ( a[i] > p / q || ( i + 1 < n && a[i] * q == p ) ) break;
29             p -= q * a[i];
30             swap( p, q );
31         }
32 
33         if ( i == n && !q ) puts("YES");
34         else puts("NO");
35     }
36     return 0;
37 }