求超级最小公倍数的疑问

    最近开始在"编程啦"上做题,不知道能坚持多久...

 

    "超级最小公倍数"题目:(地址: http://www.bianchengla.com/practise/problem?id=1001)

           

给2个正整数a,b(1<=a,b<=10^100),求a和b的最小公倍数。

   求最小公倍数的话,一般使用公式: x*y=最小公倍数*最大公约数. 而求最大公约数,也就是gcd,一般用辗转相除法和辗转相减法.

 

    辗转相除法:

 

public static BigInteger gcd(BigInteger x, BigInteger y) {
		BigInteger r;

		x = x.min(y);
		y = x.max(y);

		r = x.mod(y);

		while (!r.equals(BigInteger.ZERO)) {
			x = y;
			y = r;
			r = x.mod(y);
		}
		return y;

	}

    之所以用BigInteger,是因为题目中说b<=10¹⁰⁰,int和long都放不下. 然而在使用我自己编写的gcd函数时,我测试的几个数据都没错误,但提交的时候却老是说"结果错误".

 

    别人的能通过的代码:(来自http://hi.baidu.com/ylllxw08/blog/item/06d10585bbd55ed6bd3e1e04.html)

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
	public static void main(String args[]) {
		BigInteger a, b, c, d, e;
		String s, t;
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			s = cin.next();
			t = cin.next();
			a = new BigInteger(s);
			b = new BigInteger(t);
			e = BigInteger.valueOf(0);
			if (a.compareTo(e) == 0 && b.compareTo(e) == 0)
				break;
			c = a.gcd(b);
			d = a.multiply(b);
			System.out.println(d.divide(c));
		}
	}
}

 

    和我的代码的区别是,他用的是BigInteger提供的gcd函数,而我用的是自己写的. 我的的gcd到底哪里出错了呢?

 

评论

2 楼 sulifeng 2012-05-31  

yanhuoosg 写道

gcd函数的赋值赋错了，y=x,x=r才对啊，y是max，x是min

晕。。。老是犯低级错误。。。多谢啦

1 楼 yanhuoosg 2012-05-29  

gcd函数的赋值赋错了，y=x,x=r才对啊，y是max，x是min