Chương trình tìm UCLN cho số có 47 chữ số

[Wallace_Wu]

A/C cho em hướng giải quyết bài này với. Em viết chương trình đúng thuật toán nhưng không hiểu sao output ra không đúng ạ
-Viết chương trình tìm ƯỚc chung lớn nhất của a,b
input:
a=1221
b=1234567891011121314151617181920212223242526272829
output:
3

[noz1995 (Trần Hoàn)]

Thuật toán cho code ngắn nhất mình nghĩ được (Java)

public static BigInteger ucln(BigInteger a, BigInteger b)
{
    if(a.compareTo(BigInteger.ZERO) <= 0 || b.compareTo(BigInteger.ZERO) <= 0)
        throw new IllegalArgumentException("params must be positive");
    return a.equals(b) ? a : ucln(a.min(b), a.subtract(b).abs());
}

Đối với BigInteger thì dùng phép trừ của BigInteger là được.

Edit: Exception in thread "main" java.lang.StackOverflowError
Không xài đệ quy được, phải xài vòng lặp thôi

Edit #2: Dùng mod thì không bị

Summary

    public static BigInteger ucln(BigInteger a, BigInteger b)
    {
        if(a.compareTo(BigInteger.ZERO) <= 0 && b.compareTo(BigInteger.ZERO) <= 0)
            throw new IllegalArgumentException("At lease 1 params must be positive");
        if (a.min(b).compareTo(BigInteger.ZERO) == 0)
            return a.max(b);
        return ucln(a.min(b), a.max(b).mod(a.min(b)));
    }

[Wallace_Wu]

trong c++ mình dùng kiểu long long int mà vẫn không đúng output bạn ạ. Thử với số nhỏ thì vẫn đúng. Mình đang phân vân chỗ kiểu dữ liệu ý

[SITUVN.gcd]

Kiểu unsigned long long int thì cũng chỉ tối đa là 18446744073709551615 (2^64-1) (20 chữ số).

Bạn kiếm thư viện nào đó hỗ trợ số lớn hơn.

[Wallace_Wu]

Bạn có biết thư viện nào chỉ mình với, mình với ạ?

[rogp10]

Trừ thì chừng nào mới ra

[noz1995 (Trần Hoàn)]

Thì thay bằng mod =]]

[SITUVN.gcd]

“Thư viện” Google: c++ biginteger library.

[tntxtnt]

mingw/gcc thì em xài gmpxx, còn msvc thì mpir :V