Euclid Problem - PC110703

2022-10-27 07:30:08

欢迎访问我的新博客：http://www.milkcu.com/blog/

原文地址：http://www.milkcu.com/blog/archives/uva10104.html

原创：Euclid Problem - PC110703

作者：MilkCu

题目描述

Euclid Problem

The Problem

From Euclid it is known that for any positive integers A and Bthere exist such integersX andY that
AX+BY=D,where D is the greatest common divisor ofA andB.The problem is to find for given
A and B correspondingX,Y and D.

The Input

The input will consist of a set of lines with the integer numbers A andB, separated with space (A,B<1000000001).

The Output

For each input line the output line should consist of threeintegers X, Y andD, separated with space. If there are severalsuchX and
Y, you should output that pair for which|X|+|Y| is the minimal (primarily) andX<=Y (secondarily).

Sample Input

4 6

17 17

Sample Output

-1 1 2

0 1 17

解题思路

本题考查的是求解最大公约数（greatest common divisor，也称gcd）的欧几里得（Euclid）算法。

Euclid算法建立在两个事实的基础上：

1. 如果b|a（b整除a），则gcd(a, b) = b；

2. 如果存在整数t和r，使得a = bt + r，则gcd(a, b) = gcd(b, r)。

Euclid算法是递归的，它不停的把较大的整数替换为它除以较小整数的余数。

Euclid算法指出，存在x和y，使

a * x + b * y = gcd(a, b)

又有

gcd(a, b) = gcd(b, a % b)

为了方便计算，我们将上式写为

gcd(a, b) = gcd(b, a - b * floor(a / b))

假设我们已经找到整数x'和y'，使得

b * x' + (a - b * floor(a / b)) * y' = gcd(a, b)

整理上式，得到

a * y' + b * (x' - b * floor(a / b) * y') = gcd(a, b)

与a * x + b * y = gcd(a, b)相对应，得到

x = y'

y = x' - floor(a / b) * y'

代码实现

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

int gcd(int a, int b, int & x, int & y) {

	int x1, y1;

	if(a < b) {

		return gcd(b, a, y, x);

	}

	if(b == 0) {

		x = 1;

		y = 0;

		return a;

	}

	int g = gcd(b, a % b, x1, y1);

	x = y1;

	y = x1 - floor(a / b) * y1;

	return g;

}

int main(void) {

	int a, b;

	while(cin >> a >> b) {

		int x, y;

		int g = gcd(a, b, x, y);

		cout << x << " " << y << " " << g << endl;

	}

	return 0;

}

（全文完）

本文地址：http://blog.csdn.net/milkcu/article/details/23590217

码农公寓