ZOJ-3593-One Person Game（拓展欧几里得）

45 阅读 0 评论 30 点赞

我是靠谱客的博主成就冥王星，最近开发中收集的这篇文章主要介绍ZOJ-3593-One Person Game（拓展欧几里得），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

One Person Game

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.

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. (-231 ≤ A, B < 231, 0 < a, b < 231)

Output

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

Sample Input

2
0 1 1 2
0 1 2 4

Sample Output

1
-1

解题思路：

拓展中国剩余定理。
但是求出来的x，y不一定是最优解。
最优解要让步数尽可能少。已知。a+b可以合成为一步。那么就是要找 x，y最接近的解。
先求出通解。
然后求出x，y最近的两个点。
枚举这两个点，选最小值就结束了。

AC代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%dn", n)
#define pc(n) printf("%c", n)
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lldn", n)
#define pldd(n,m) printf("%lld %lldn", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sc(n) scanf("%c",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mem(a,n) memset(a, n, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mod(x) ((x)%MOD)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) (x&-x)
#define pii map<int,int>
#define mk make_pair
#define rtl rt<<1
#define rtr rt<<1|1
#define Max(x,y) (x)>(y)?(x):(y)
#define int long long
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const ll mod = 10007;
const double eps = 1e-9;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
//const int inf = 0x3f3f3f3f;
inline int read(){int ret = 0, sgn = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')sgn = -1;ch = getchar();}
while (ch >= '0' && ch <= '9'){ret = ret*10 + ch - '0';ch = getchar();}
return ret*sgn;}
inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');}
int qpow(int m, int k, int mod){int res=1%mod,t=m%mod;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;}
ll gcd(ll a,ll b){if(b > a) swap(a,b); return b==0?a : gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll inv(ll x,ll mod){return qpow(x,mod-2,mod)%mod;}
const int N = 1e6+15;
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(!b) d=a, x=1, y=0;
else{
exgcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int excrt(int r[], int m[], int n)
{
int M = m[0], R = r[0], x, y, d;
for (int i = 1; i < n; ++i)
{
exgcd(M, m[i], d, x, y);
if ((r[i] - R) % d) return -1;
x = (r[i] - R) / d * x % (m[i] / d);
R += x * M;
M = M / d * m[i];
R %= M;
}
return R > 0 ? R : R + M;
}
signed main()
{
int t = 1,cas = 1;
cin>>t;
int A,B,a,b;
while(t --)
{
cin>>A>>B>>a>>b;
int x,y,d;
int dis = abs(B-A);
exgcd(a,b,d,x,y);
if(dis%d != 0)
cout<<-1<<endl;
else
{
if(x > y){swap(x,y);swap(a,b);}
x *= dis/d;y *= dis/d;
int t = (y-x)*d/(a+b);
a /= d; b /= d;
int ans1 = (1ll<<40);
int ans2 = (1ll<<40);
for(int i = t; i <= t+1; i ++)
{
int t1 = x+b*i;
int t2 = y-a*i;
if(t1*t2 <= 0)
ans2 = abs(t1)+abs(t2);
else{
if(t1)
ans2 = max(t1,t2);
else
ans2 = -min(t1,t2);
}
ans1 = min(ans1,ans2);
}
cout<<ans1<<endl;
}
}
}