UVALive - 6428（扩展欧几里德）

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=48388

前段时间偶然碰到的一道题，今天突然想到没把它记录下来。

比较不错的扩展欧几里德求解的应用

题意求是否满足ax+by=c gcd(a,b）==1 a>=0&&b>=0

数比较大在求解时LL会溢出，用JAVA改写了一遍程序。

扩展欧几里德可以求出一组满足条件的解p= p1+b/gcd(a,b)*t q = q1+a/gcd(a,b)*t （t为任意整数）

因为上面的解有条件所以根据p>=0 q>=0可以确定出来t的范围在范围内枚举t可以求出解来判断是否满足条件即可。

注意一下特殊情况，为0的情况。

  1 import java.text.*;
  2 import java.io.*;
  3 import java.util.*;
  4 import java.math.*;
  5 import java.applet.*;
  6 public class Main 
  7 {
  8     static BigInteger x,y,o = BigInteger.valueOf(0),o1 = BigInteger.valueOf(1);
  9     static BigInteger gcd(BigInteger a,BigInteger  b)
 10     {
 11         if(b.compareTo(BigInteger.valueOf(0))==0)
 12             return a;
 13         else
 14             return gcd(b,a.mod(b));
 15     }
 16     static BigInteger exgcd(BigInteger a,BigInteger b)
 17     {
 18         if(b.compareTo(o)==0)
 19         {
 20             x = o1; y = o; return a;
 21         }
 22         BigInteger d = exgcd(b,a.mod(b));
 23         BigInteger temp = x;
 24         x = y;
 25         y = temp.subtract(a.divide(b).multiply(y))  ;
 26         return d;
 27     }
 28     public static void main(String[] args)
 29     {
 30         Scanner  cin = new Scanner(System.in);
 31         BigInteger a,b,c;
 32         while(cin.hasNext())
 33         {
 34             a = cin.nextBigInteger();
 35             b = cin.nextBigInteger();
 36             c = cin.nextBigInteger();
 37             if(c.compareTo(a)<0&&c.compareTo(b)<0)
 38             {
 39                 System.out.println("NO");
 40                 continue;
 41             }
 42             BigInteger o = BigInteger.valueOf(0);
 43             if(a.compareTo(o)==0||b.compareTo(o)==0)
 44             {
 45                 if(a.compareTo(o)==0&&b.compareTo(o)==0)
 46                 {
 47                     if(c.compareTo(o)==0)
 48                     System.out.println("YES");
 49                     else
 50                     System.out.println("NO");
 51                 }
 52                 else if(a.compareTo(o)==0)
 53                 {
 54                     if(c.mod(b).compareTo(o)==0)
 55                     System.out.println("YES");
 56                     else
 57                     System.out.println("NO");
 58                 }
 59                 else
 60                 {
 61                     if(c.mod(a).compareTo(o)==0)
 62                     System.out.println("YES");
 63                     else
 64                     System.out.println("NO");
 65                 }
 66                 continue;
 67             }
 68             if(c.compareTo(b)==0||c.compareTo(a)==0)
 69             {
 70                 System.out.println("YES");
 71                 continue;
 72             }
 73             BigInteger t = gcd(a,b);
 74             if(c.mod(t).compareTo(o)!=0)
 75             {
 76                 System.out.println("NO");
 77                 continue;
 78             }
 79             exgcd(a,b);
 80             x = x.multiply(c.divide(t));
 81             y = y.multiply(c.divide(t));
 82             BigInteger k1 = b.divide(t);
 83             BigInteger k2 = a.divide(t);
 84             int flag = 0;
 85             BigInteger tx=x,ty=y;
 86             BigInteger f1 = (x.multiply(BigInteger.valueOf(-1))).divide(k1).subtract(BigInteger.valueOf(1));
 87             BigInteger f2 = y.divide(k2).add(BigInteger.valueOf(1));
 88             BigInteger e = f1;
 89             while(e.compareTo(f2)<=0)
 90             {
 91                 tx = k1.multiply(e).add(x);
 92                 ty = k2.multiply(e);
 93                 ty = y.subtract(ty);
 94                 if(tx.compareTo(o1)>=0&&ty.compareTo(o1)>=0)
 95                 {
 96                     if(gcd(tx,ty).compareTo(BigInteger.valueOf(1))==0)
 97                     {
 98                         //System.out.println(tx+" "+ty);
 99                         flag = 1;
100                         break;
101                     }
102                 }
103                 e = e.add(BigInteger.valueOf(1));
104             }
105             if(flag==1)
106             System.out.println("YES");
107             else
108             System.out.println("NO");
109         }
110     }
111 }

View Code

秒客网

UVALive - 6428（扩展欧几里德）

相关文章