题目地址:http://codeforces.com/problemset/problem/305/B
题目意思:
就是给你一个p/q,然后再给你一个可化简的分式,问你是否相等
之前我有同学,用正着做的方法做出来了,
没有倒着做的原因是数字会太大,从而WA
今天在整理大数模板的时候,用大数模板水过了。HEHE
下面上JAVA代码:
import java.math.BigInteger; import java.util.Scanner; public class Main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BigInteger p,q; BigInteger a[] = new BigInteger[100]; Scanner cin = new Scanner(System.in); p=cin.nextBigInteger(); q=cin.nextBigInteger(); int n = cin.nextInt(); for(int i=1;i<=n;i++) { a[i]=cin.nextBigInteger(); } if(n==1)//这里要特判一下 { BigInteger tmp = p.gcd(q); p=p.divide(tmp); q=q.divide(tmp); if(q.equals(BigInteger.ONE) && p.equals(a[1]) ) System.out.println("YES"); else System.out.println("NO"); System.exit(0); } BigInteger x,y; x=BigInteger.ONE; y=a[n]; for(int i=n-1;i>=2;i--) { x=a[i].multiply(y).add(x); BigInteger tmp = x; x=y; y=tmp; } if(n>=2) { x=a[1].multiply(y).add(x); } BigInteger tmp; tmp = p.gcd(q); p=p.divide(tmp); q=q.divide(tmp); tmp=x.gcd(y); x=x.divide(tmp); y=y.divide(tmp); //System.out.println(p); //System.out.println(q); //System.out.println(x); //System.out.println(y); if(x.equals(p) && y.equals(q)) System.out.println("YES"); else System.out.println("NO"); System.exit(0); } }