ZOJ 3593.One Person Game-扩展欧几里得(exgcd)

智障了，智障了，水一水博客。

本来是个水题，但是for循环遍历那里写挫了。。。

One Person Game

Time Limit: 2 Seconds Memory Limit: 65536 KB

There is an interesting and simple one person game. Suppose there is a number axis under your feet. You are at point A at first and your aim is point B. There are 6 kinds of operations you can perform in one step. That is to go left or right by a,b and c, here c always equals to a+b.

You must arrive B as soon as possible. Please calculate the minimum number of steps.

Input

There are multiple test cases. The first line of input is an integer T(0 < T ≤ 1000) indicates the number of test cases. Then T test cases follow. Each test case is represented by a line containing four integers 4 integers A, B, a and b, separated by spaces. (-2³¹ ≤ A, B < 2³¹, 0 < a, b < 2³¹)

Output

For each test case, output the minimum number of steps. If it's impossible to reach point B, output "-1" instead.

Sample Input

Sample Output

1

-1

一开始没看懂题，后来懂了，c=a+b，所以就有3个方程，分别是a*x+b*y=r,a*x+c*y=r,b*x+c*y=r;

扩展欧几里得求出来gcd之后，通过判断r是不是gcd的倍数得到方程有没有解，然后 go on。。。

因为扩展欧几里得求出来的x和y并不是最优解，所以通过x和y的通式，x=x₀+b/gcd*k;y=y₀-a/gcd*k;(k为倍数)

本来自己想的是最优解和求出来的一般解应该差不了多少，就直接从-100到100遍历的，结果发现一直wa，学长说要找方程所在直线与源点距离最近的才是结果。

就是确定一下for的范围，不是瞎想的-100到100就以为能水过去。。。

首先x=x₀+b/gcd*k，求出来k的范围，就是[-x₀*gcd/b-1,-x₀*gcd/b+1]，在这个范围内for一遍，然后再通过y的通解，求出来的k的范围再for一遍就得到最优解了。

我智障，算y的k的时候，应该/a，我写成/b了_(:з」∠)_

代码:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const int inf=0x3f3f3f3f;

 const int eps=1e-;

 ll exgcd(ll a,ll b,ll &x,ll &y){

     if(b==){

         x=;y=;

         return a;

     }

     ll r=exgcd(b,a%b,x,y);

     ll t=y;

     y=x-(a/b)*y;

     x=t;

     return r;

 }

 ll fun(ll a,ll b,ll r){

     ll x,y;

     ll gcd=exgcd(a,b,x,y);

     if(r%gcd!=)return -;

     else{

         x*=r/gcd;

         y*=r/gcd;

         ll k1=-1.0*x*gcd/b-,k2=-1.0*x*gcd/b+;

         ll kk1=1.0*y*gcd/a-,kk2=1.0*y*gcd/a+;//y是除以a，智障了，写成除以b了。

         ll ans=fabs(x)+fabs(y);

         for(ll i=k1;i<=k2;i++){

             if(fabs(x+i*b/gcd)+fabs(y-i*a/gcd)<ans)

                 ans=fabs(x+i*b/gcd)+fabs(y-i*a/gcd);

         }

         for(ll i=kk1;i<=kk2;i++){

              if(fabs(x+i*b/gcd)+fabs(y-i*a/gcd)<ans)

                 ans=fabs(x+i*b/gcd)+fabs(y-i*a/gcd);

         }

         return ans;

     }

 }

 int main(){

     int t;

     cin>>t;

     while(t--){

         ll A,B,a,b,c;

         cin>>A>>B>>a>>b;

         c=a+b;

         ll r=fabs(A-B);

         ll h1=fun(a,b,r);

         ll h2=fun(a,c,r);

         ll h3=fun(b,c,r);

         if(h1==-&&h2==-&&h3==-)cout<<"-1"<<endl;

         else{

             ll ans=min(h1,h2);

             ans=min(ans,h3);

             cout<<ans<<endl;

         }

     }

 }

水一水，溜了，慢慢补。去看主席树了。。。

巴特西

ZOJ 3593.One Person Game-扩展欧几里得(exgcd)

Input

Output

Sample Input

Sample Output

最新文章

热门文章