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的情况。

 import java.text.*;

 import java.io.*;

 import java.util.*;

 import java.math.*;

 import java.applet.*;

 public class Main

 {

     static BigInteger x,y,o = BigInteger.valueOf(0),o1 = BigInteger.valueOf(1);

     static BigInteger gcd(BigInteger a,BigInteger  b)

     {

         if(b.compareTo(BigInteger.valueOf(0))==0)

             return a;

         else

             return gcd(b,a.mod(b));

     }

     static BigInteger exgcd(BigInteger a,BigInteger b)

     {

         if(b.compareTo(o)==0)

         {

             x = o1; y = o; return a;

         }

         BigInteger d = exgcd(b,a.mod(b));

         BigInteger temp = x;

         x = y;

         y = temp.subtract(a.divide(b).multiply(y))  ;

         return d;

     }

     public static void main(String[] args)

     {

         Scanner  cin = new Scanner(System.in);

         BigInteger a,b,c;

         while(cin.hasNext())

         {

             a = cin.nextBigInteger();

             b = cin.nextBigInteger();

             c = cin.nextBigInteger();

             if(c.compareTo(a)<0&&c.compareTo(b)<0)

             {

                 System.out.println("NO");

                 continue;

             }

             BigInteger o = BigInteger.valueOf(0);

             if(a.compareTo(o)==0||b.compareTo(o)==0)

             {

                 if(a.compareTo(o)==0&&b.compareTo(o)==0)

                 {

                     if(c.compareTo(o)==0)

                     System.out.println("YES");

                     else

                     System.out.println("NO");

                 }

                 else if(a.compareTo(o)==0)

                 {

                     if(c.mod(b).compareTo(o)==0)

                     System.out.println("YES");

                     else

                     System.out.println("NO");

                 }

                 else

                 {

                     if(c.mod(a).compareTo(o)==0)

                     System.out.println("YES");

                     else

                     System.out.println("NO");

                 }

                 continue;

             }

             if(c.compareTo(b)==0||c.compareTo(a)==0)

             {

                 System.out.println("YES");

                 continue;

             }

             BigInteger t = gcd(a,b);

             if(c.mod(t).compareTo(o)!=0)

             {

                 System.out.println("NO");

                 continue;

             }

             exgcd(a,b);

             x = x.multiply(c.divide(t));

             y = y.multiply(c.divide(t));

             BigInteger k1 = b.divide(t);

             BigInteger k2 = a.divide(t);

             int flag = 0;

             BigInteger tx=x,ty=y;

             BigInteger f1 = (x.multiply(BigInteger.valueOf(-1))).divide(k1).subtract(BigInteger.valueOf(1));

             BigInteger f2 = y.divide(k2).add(BigInteger.valueOf(1));

             BigInteger e = f1;

             while(e.compareTo(f2)<=0)

             {

                 tx = k1.multiply(e).add(x);

                 ty = k2.multiply(e);

                 ty = y.subtract(ty);

                 if(tx.compareTo(o1)>=0&&ty.compareTo(o1)>=0)

                 {

                     if(gcd(tx,ty).compareTo(BigInteger.valueOf(1))==0)

                     {

                         //System.out.println(tx+" "+ty);

                         flag = 1;

                         break;

                     }

                 }

                 e = e.add(BigInteger.valueOf(1));

             }

             if(flag==1)

             System.out.println("YES");

             else

             System.out.println("NO");

         }

     }

 }

巴特西

UVALive - 6428（扩展欧几里德）

最新文章

热门文章