ACM:数论专题——拓展欧几里得

题目描述：
小Hi和小Ho周末在公园溜达。公园有一堆围成环形的石板，小Hi和小Ho分别站在不同的石板上。已知石板总共有m块，编号为 0..m-1，小Hi一开始站在s1号石板上，小Ho一开始站在s2号石板上。小Ho每次移动v1块，小Hi移动v2块。求最少经过多长时间，两人可以到达同一块石板。

解答：
假设两人经过t时间后，就会相遇，那么，我们就可以列出如下的方程：

s1 + v1 × t = s2 + v2 × t - km.................................(i)

这表明：当两人到达同一位置时，其中一人恰好比另一人多走了k圈。对上面的方程整理一下，可得：

(v1 - v2) × t + mk = s2 - s1.................................(ii)

于是，题目中的问题就转化为求解以上方程解的问题。根据题意，上式中的m和t一定是正整数，只要能找到上面方程的一组正整数解，同时使得t的值尽可能小，就是本题的结果。如果方程无正整数解，则本题就无解，即两人永远不会相遇。

·判定：
判定以上的方程是否有整数解用到了拓展欧几里得定理。定理内容如下：
二元一次方程：Ax + By = C (A, B, C >0）。它有无数个解，但有整数解的条件是：C可以被A和B的最大公约数整除(证明不会 ACM:数论专题——拓展欧几里得

)。即：C % gcd(A, B) = 0 <=> 方程 Ax + By = C 有整数解。
对应于上面的式(ii)，参数A即为(v1-v2), B即为m，C即为s2 - s1，而x就是t，y即为k。

式中m一定是整数，而如果v2 > v1,那么将上述方程改为：

s1 + v1 × t - km = s2 + v2 × t

即可。而如果s2-s1是负数的话，就将原式改为：

s1 + v1 × t = s2 + v2 × t + m - (k+1)m

由于方程中k是未知数，所以上式可以改为：

s1 + v1 × t = s2 + v2 × t + m - km

再整理，可得：

(v1 - v2) × t + mk = s2 - s1 + m

这样就可以保证方程中的参数：A, B, C 一定都是正整数，就可以使用拓展欧几里得定理判定了。
数字A B的最大公约数可以使用辗转相除法进行求解：
记 A B (A ≥ B) 的最大公约数是gcd(A,B),那么：
    如果A可以被B整除，那么：gcd(A, B) = B。
      如果A不可以被B整除，那么：gcd(A,B) = gcd(B, A%B)。
因此求解最大公约数的过程如下：
(1) 如果A可以被B整除，gcd(A,B) = B.求解结束；否则执行步骤(2)。
(2) 如果A不可以被B整除，令：A = B， B = A%B,执行步骤(1)。

如果判定无解，就可以直接输出结果。

·求解：
    如果利用拓展欧几里得定理判定的结果是方程有整数解，那么接下来的任务是，找到方程的一组整数解，方法如下：
首先考虑方程：
            Ax + By = gcd(A, B)...............................①
和方程：
            Bx + (A%B)y = gcd(B, A%B)........................②
如果我们知道方程②的一组解为(x2, y2)，即：
            Bx2 + (A%B)y2 = gcd(B, A%B)
        => Bx2 + [A - (A/B)×B]y2 = gcd(B, A%B)
      => Bx2 + Ay2 - B×(A/B)y2 = gcd(B, A%B)
      => B×[x2 - (A/B)y2] + Ay2 = gcd(B, A%B)................③
根据辗转相除法，可以发现： gcd(A,B) = gcd(B, A%B),于是③式就可以转化为：
            Ay2 + B×[x2 - (A/B)y2] = gcd(A,B)...................④
于是，对比式④和式①，我们就可以得到：
            x1 = y2
          y1 = x2 - (A/B)y2
是方程①的一组解。

最后，说明一种特殊情况，如果A可以被B整除：A = aB,那么：gcd(A, B) = B,同时方程①可以转化为：
            aBx + By = B
      => ax + y = 1
该方程的一组解是：
            x = 0
          y = 1

至此，可以总结求解方程：Ax + By = C 的一组整数解的步骤如下：
      (1) 将参数A B C 同时除以gcd(A,B), 得到方程：A'x + B'y = C'，执行步骤(2)。
      (2) 求解方程：F0: A'x + B'y = 1，此时A' 和 B' 一定是互质的，gcd(A', B') = 1.然后迭代执行步骤(3) (4) (5),即第i轮迭代时的方程为Fi。
      (3) 判定方程Fi中的A'是否可以被B'整除，如果可以整除，执行步骤(4)，否则执行步骤(5)。
      (4) 如果方程Fi中的A'可以被B'整除，那么得到一组解：Ai: x = 0, y = 1。然后执行步骤(6)。

      (5) 如果方程Fi中的A'不可以被B'整除，那么令A' = B', B' = A'%B',得到方程Fi+1, 执行步骤(3)。
      (6) 得到方程Fi的解Ai：x=0, y=1后，令：x = y, y = x - (A'/B')y,得到方程Fi-1的解Ai-1。注意，式中的A'和B'是方程Fi-1的参数。执行步骤(7)。
      (7) 反复执行步骤(6)，知道得到F0的解A0：x=x0, y=y0。
      (8) 将A0乘以C',就是方程A'x + B'y = C'的解，也就是原方程Ax + By = C的解。即：

x = C'x0
y = C'y0

以上是求解方程整数解的过程。

·解优化：

以上方法只能保证得到一组整数解，但不能确保得到的解释我们需要的答案。根据上面题意，我们需要的是方程(ii)的整数解，同时，要使得t尽可能地小。优化方式如下：
假设已经得到了方程：Ax + By = C 的一个解：x y，那么：
          Ax + By = C
      => Ax + By - kAB + kAB = C
       => A(x'-kAB) + B(y'+kAB) = C ................................⑤
      => A(x'+kAB) + B(y'-kAB) = C ................................⑥
其中：k为任意整数。
    根据⑤、⑥式可得，如果：x',y'是原方程的一组解，那么：x'+kAB， y'-kAB 以及 x'-kAB, y'+kAB 也是方程的解。利用这个性质，就可以找到我们需要的最优的一组解，即为本题的答案。

输入输出格式：
  输入：第1行：每行5个整数s1,s2,v1,v2,m，
                0 ≤ v1,v2 ≤ m ≤ 1,000,000,000
                0 ≤ s1,s2 < m

中间过程可能很大，最好使用64位整型。
输出：输出1行，输出1个整数，表示解，若该组数据无解则输出-1。

程序代码：

/****************************************************/
/* File        : Hiho_Week_95.cpp                   */
/* Author      : Zhang Yufei                        */
/* Date        : 2016-04-25                         */
/* Description : HihoCoder ACM program. (submit:g++)*/
/****************************************************/

#include<stdio.h>
#include<stdlib.h>

typedef struct node {
	long long x;
	long long y;
} result;

// Record the input data.
int s1, s2, v1, v2, m;

/*
 * This function computes the greast common divisor of 2 
 * given numbers.
 * Parameters:
 *		@a & &b: The 2 numbers to compute.
 * Returns:
 *		The greatest common divisor of &a and &b.
 */
long long gcd(long long a, long long b);

/*
 * This function calculates the result.
 * Parameters:
 *		@a & @b: The parameters of A, B in: Ax + By = 1.
 * Returns:
 *		The result of the equation.
 */
result* compute(long long a, long long b);
		
/*
 * The main program.
 */
int main (void) {
	scanf("%d %d %d %d %d", &s1, &s2, &v1, &v2, &m);
	
	long long A, B, C;
	
	A = m;
	if(v2 > v1) {
		B = v1 - v2 + m;
		C = s2 - s1;
	} else {
		B = v2 - v1 + m;
		C = s1 - s2;
	}
	
	long long D = gcd(A, B);
	
	if(C % D != 0) {
		printf("-1\n");
		return 0;
	}
	
	A /= D;
	B /= D;
	C /= D;
	
	result *r = compute(A, B);
 	
 	long long y = r->y;
 	y *= C;
 	y %= A;
 	
 	while(y <= 0) {
	 	y += A;
	}
	
	printf("%lld\n", y);
	
	return 0;
	
} 

/*
 * This function computes the greast common divisor of 2 
 * given numbers.
 * Parameters:
 *		@a & &b: The 2 numbers to compute.
 * Returns:
 *		The greatest common divisor of &a and &b.
 */
long long gcd(long long a, long long b) {
	if(a % b == 0) {
		return b;
	} else {
		return gcd(b, a % b);
	}
}

/*
 * This function calculates the result.
 * Parameters:
 *		@a & @b: The parameters of A, B in: Ax + By = 1.
 * Returns:
 *		The result of the equation.
 */
result* compute(long long a, long long b) {
	result *r;
	if(a % b == 0) {
		r = (result*) malloc(sizeof(result));
		r->x = 0;
		r->y = 1;
	} else {
  		r = compute(b, a % b);
  		long long x = r->y;
  		long long y = r->x - a / b * r->y;
  		r->x = x;
  		r->y = y;
	}
	
	return r;
}

秒客网

ACM:数论专题——拓展欧几里得

相关文章