One Person Game(zoj3593+擴展歐幾裡德)，personzoj3593
One Person Game
Time Limit:2000MS
Memory Limit:65536KB
64bit IO Format:%lld & %llu
Submit Status Practice ZOJ 3593
Description
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 toa+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. (-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
題意：一維坐標軸，有A和B兩個地方，現在從A到B，每次可以向任意方向走a、b或者c的距離，其中c=a+b，問能不能走到B，能的話最少走幾次。
思路：c = a+b, C = A-B，則等價於求{|x|+|y| | ax+by=C || ax+cy=C || bx+cy=C}。對於ax+by=C，
用擴展歐幾裡得算法求得ax+by=gcd(a,b)，是否有解可由C是否為gcd的倍數判斷。
若有解，原方程的一組解為(x0, y0) = (xx*C/gcd, yy*C/gcd)。
令am=a/gcd，bm=b/gcd，則通解可表示為(x0+k*bm, y0-k*am)。
能使|x|+|y|最小的整點一定是最靠近直線與坐標軸交點的地方，
可以由|x|+|y|=C的圖像不斷平移看出。
由於負數取整時是先對它的絕對值取整，再添上負號，
所以考慮的范圍要是[-x0/bm-1, -x0/bm+1] 、[y0/am-1, y0/am+1]。
轉載請注明出處：
尋找&星空の孩子
![]()
1 #include<stdio.h>
2 #include<math.h>
3 #include<algorithm>
4 #define LL long long
5 using namespace std;
6
7 LL ans;
8 void exgcd(LL a,LL b,LL& d,LL& x,LL& y)
9 {
10 if(!b){d=a;x=1;y=0;}
11 else
12 {
13 exgcd(b,a%b,d,y,x);
14 y-=x*(a/b);
15 }
16 }
17 LL China(LL a,LL b,LL c)
18 {
19 LL x,y,d,bm,am;
20
21 exgcd(a,b,d,x,y);
22 if(c%d) return -1;
23 bm=b/d;
24 am=a/d;
25 x=x*c/d;
26 y=y*c/d;
27
28
29 LL sum=fabs(x)+fabs(y);
30
31 for(int i=-x/bm-1;i<=-x/bm+1;i++)
32 {
33 LL X=x+bm*i;
34 LL Y=y-am*i;
35 if(i)
36 {
37 LL tmp=fabs(X)+fabs(Y);
38 if(tmp<sum) sum=tmp;
39 }
40 }
41 for(int i=y/am-1;i<=y/am+1;i++)
42 {
43 LL X=x+bm*i;
44 LL Y=y-am*i;
45 if(i)
46 {
47 LL tmp=fabs(X)+fabs(Y);
48 if(tmp<sum) sum=tmp;
49 }
50 }
51 return sum;
52 }
53
54
55 int main()
56 {
57 int T;
58 LL A,B,C,a,b,c,d,x,y;
59 scanf("%d",&T);
60 while(T--)
61 {
62 scanf("%lld%lld%lld%lld",&A,&B,&a,&b);
63 c=a+b;
64 C=fabs(A-B);
65
66 LL t1=China(a,b,C);
67 LL t2=China(a,c,C);
68 LL t3=China(b,c,C);
69
70 if(t1==-1&&t2==-1&&t3==-1)
71 {
72 printf("-1\n");
73 continue;
74 }
75 if(t1>t2) ans=t2;
76 else ans=t1;
77
78 if(ans>t3) ans=t3;
79
80 printf("%lld\n",ans);
81 }
82 return 0;
83 }
View Code
