最近开始在"编程啦"上做题,不知道能坚持多久...
"超级最小公倍数"题目:(地址: 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到底哪里出错了呢?
分享到:
相关推荐
用LabVIEW求最大公约数和最小公倍数。可以自行选择数据。
求解最小公倍数的几种方法,c++算法编程等。通过最小公倍数。。。
关于如何求最大公约数和最小公倍数的c语言程序
编写求两个整数的最小公倍数的函数,函数原型为:int maxb(int x,inty);并编写主函数,调用该函数求键盘输入的两个整数的最小公倍数,并在屏幕输出。
包含了:1.辗转相除法函数嵌套流程图2.辗转相除法函数递归流程图3.穷举法求最小公倍数流程图4.穷举法求最大公约数流程图5.更相减损术流程图
VB 用函数求最小公倍数 VB 用函数求最小公倍数
Java求最大公约数、最小公倍数,输入两个正整数m和n,求其最大公约数和最小公倍数。最小公倍数可由原数除以最大公约数计算得到,这里使用了辗除法。
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
实现求两个整数的最大公约数和最小公倍数。求两个数的最大公约数和最小公倍数的方法有很多种,常用的有欧几里得算法和Stein算法。
vba求最小公倍数
python 输入两个正整数计算最大公约数和最小公倍数 示例
1.最小公倍数、最大公约数1.最小公倍数、最大公约数1.最小公倍数、最大公约数
def lcm(a,b): for i in range(min(a,b),0,-1): if a%i==0 and b%i==0: return a*b//i c=int(input("请输入第一个数:")) d=int(input("请输入第二个数:")) print("这两个数的最小公倍数:") print(lcm(c,d))
基于FPGA开发板的两位数求最大公约数和最小公倍数的设计,该设计中利用辗转相减法求得公约数与公倍数,且两个数的数值可通过按键修改,设计灵活可靠。该设计基于vivado开发,并带有testbench文件,方便仿真学习。
计算任意几个数的最小公倍数和最大公约数(简单方式\有子VI)
求两个整数的最大公约数和最小公倍数的C语言方法
包含:1、辗转相除法函数嵌套盒图2、辗转相除法函数递归盒图3、穷举法求最小公倍数盒图4、穷举法求最大公约数流程图
今天在课堂上,老师讲解了如何求两个正整数c1和c2的最大公约数和最小公倍数。现在Hankson认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知...
求最大公约数和最小公倍数的程序,求两个整数的最大公约数和最小公倍数!