求超级最小公倍数的疑问

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

?

??? "超级最小公倍数"题目:(地址: 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<=10100,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到底哪里出错了呢?

?

1 楼 yanhuoosg 2012-05-29 gcd函数的赋值赋错了，y=x,x=r才对啊，y是max，x是min 2 楼 sulifeng 2012-05-31 yanhuoosg 写道gcd函数的赋值赋错了，y=x,x=r才对啊，y是max，x是min
晕。。。老是犯低级错误。。。多谢啦