用java求超大数最大公约数问题

Question

求俩个数最大公约数要是一般的数我都会求，可如果数字超大，而且还不允许用大数类，那该怎么办呢？新手，求老师帮忙，谢谢！java

Answer 1

不用 BigInteger 的话，你用字符串来表示这个数么？

Answer 2

两个数字都除以某个数转变成为double类型的，然后。行不行呢

Answer 3

你可以看BigInteger类是怎么计算大数的    /**
     * Calculate GCD of this and b. This and b are changed by the computation.
     */
    MutableBigInteger hybridGCD(MutableBigInteger b) {
        // Use Euclid's algorithm until the numbers are approximately the
        // same length, then use the binary GCD algorithm to find the GCD.
        MutableBigInteger a = this;
        MutableBigInteger q = new MutableBigInteger();        while (b.intLen != 0) {
            if (Math.abs(a.intLen - b.intLen) < 2)
                return a.binaryGCD(b);            MutableBigInteger r = a.divide(b, q);
            a = b;
            b = r;
        }
        return a;
    }
// Use Euclid's algorithm until the numbers are approximately the
        // same length, then use the binary GCD algorithm to find the GCD.
具体去看源代码吧

Answer 4

这个题目的意思非常明显，就是不允许你用数字类型的数据来进行计算而超大数，你只能够用字符来存储它，比如 ：String a="3444444444444444444444234222222343243234344344444444443433333333333333"String b="2333333333333333333334333333333333333333333333333333333333333424222222"而根据最大公约数的推倒公式，可以知道需要a,b两数来做除法和取余数，所以现在的问题就是如何让数字的字符串来做除法和取余数，其实这是可以的！我们完全可以用一个递归的函数来模拟除法，比如：public void getCommonDivisor(String a,String b) {
 为了便于说明算法，我这里将a,b假设成比较小的数，超大数一样
a="342";
b="23"
 首先判断a的第一个字母是否大于b的第一个字母，这里大于(不大于的情况，稍做处理即可)
 得到3>2，条件为真，接下来可以取得一个数t,使得t*2 > 3,很显然这里取得t=2
 这样我们就可以得到另外一个数n = t-1,然后将b里的每个字符乘以n就得到一个数c
 再用左对齐的方式使用a-c就可以得到一个数,将这个数赋值成a，递归上面的方式，就可以了
 简单列举下过程如下：
 a="342"
 b="23"
根据上面的思想，得到 34 - 23*1 =11 (这里n=1) 所以第一趟递归结束后得到
 a="112"
 b="23"
第二趟 112-23*4 = 20 (n=4) 结束后
a=20
b=23
由于b已经大于a，退出递归，从而我们也得到了字符"342" 除以 "23" 商等于14(n连接起来的数)
余数是20，这样就完成了字符串的除法
然后将赋值：a=34 b=20 继续调用上面的方法，就可以求出最大公约数了}