Tính a ^ b mod M với a, b lớn

[HML (MHL)]

(a ^ b) % M
M = 1000000007 (1e9 + 7)
a, b <= 10^18
cho em hỏi có cách nào để chuyển phép toán trên ra chuỗi rồi in ra không?

[noname00 (HK boy)]

M = 1e9 + 7 là số nguyên tố rồi.

Bạn tìm hiểu về thuật toán tính số mũ (có mod) nhanh:

drgnz/DNHWiki/blob/master/Algorithm/Math/Modulo/modulo.md

Ngoài ra, (a ^ b) % M = ((a % M) ^ b) % M.

[HML (MHL)]

Scanner k=new Scanner(System.in);


long a=k.nextLong();
long b=k.nextLong();
int M=M = 1000000007 ;
long kq=(long)(Math.pow(a%M, b)%M);
System.out.println(kq);

nhập vào a=10^18, b=10^18 thì kq =0

[noname00 (HK boy)]

Khi nhân 2 số lớn như vậy, đừng dùng pow, vì dùng pow sẽ rất dễ xảy ra tràn số.
(10^18)^(10^18) = 10^(18 * 10^18), quá to.

[Gio (Gió)]

long ans = BigInteger.valueOf(a).modPow(BigInteger.valueOf(b),BigInteger.valueOf(M)).longValue();

[tntxtnt]

• Đặt x = a % m. Ta có a^b ≡ x^b (mod m)
  Bước này giảm a từ 10¹⁸ xuống x còn cỡ ~10⁹
• Định lý Fermat nhỏ cho biết: a^p ≡ a (mod p) với a bất kì và p là số nguyên tố,
  • hay nói cách khác a^p-1 ≡ 1 (mod p),
  • hay a^q(p-1) ≡ 1^q ≡ 1 (mod p),
  • hay a^{q(p-1) + r} = a^q(p-1)a^r ≡ 1 * a^r (mod p) = a^r (mod p).
• Đặt r = b % (m - 1). Ta có x^b ≡ x^r (mod m) với m là số nguyên tố.
  Bước này giảm b từ 10¹⁸ xuống r còn cỡ ~10⁹

Để tính a^b lẹ thì ta xài cách tính a^b/2 * a^b/2, ở đây có mod m vẫn xài được, vì ab mod m = a mod m * b mod m.

Để tránh đệ quy thì ta phân tích b thành tổng của các số mũ 2.
Ví dụ b = 12345 thì b = 1 + 8 + 16 + 32 + 4096 + 8192, vậy a¹²³⁴⁵ = a^{1 + 8 + 16 + 32 + 4096 + 8192} = a¹a⁸a¹⁶a³²a⁴⁰⁹⁶a⁸¹⁹².

Để phân tích b ra thành tổng của các số mũ 2 thì ta chuyển b về nhị phân, từ đó ta biết được ở vị trí i nào (từ phải qua trái, bắt đầu từ 0) có số 1 thì tổng b có 1 số hạng 2ⁱ.
Ví dụ ở đây b = (12345)₁₀ = (11000000111001)₂ có số 1 ở vị trí thứ 0, 3, 4, 5, 12, 13 từ phải qua thì tổng b = 2⁰ + 2³ + 2⁴ + 2⁵ + 2¹² + 2¹³ = 1 + 8 + 16 + 32 + 4096 + 8192.

//a, b > 0, p phải là số nguyên tố
public static int modPrimePow(long a, long b, int p)
{
    long ret = 1;
    a %= p;
    b %= p - 1;
    while (b > 0) //vòng lặp phân tích b thành cơ số 2
    {
        if (b % 2 > 0)  //ở vị trí có số 1 thì nhân với a^(2^i) tương ứng. Tất cả các phép nhân đều có phép mod p theo sau.
            ret = ret * a % p;
        a = a * a % p;  //tính tiếp a^(2^(i+1)), a^1 -> a^2 -> a^4 -> a^8 -> a^16 v.v...
        b /= 2;
    }
    return (int) ret;
}

public static void main(String args[])
{
    long a = 123456789987654321L;
    long b = 546152198651652316L;
    int  m = 1000000007;
    System.out.println(modPrimePow(a, b, m)); //257419741
}

[noz1995 (Trần Hoàn)]

Java có sẵn kiểu BigInteger không mọi người? Có thì đỡ phải code.

[noname00 (HK boy)]

Có luôn anh ơi:

BigInteger Class in Java - GeeksforGeeks

Nhưng mà nếu dùng BigInteger thì có vẻ không được ổn lắm.

[khanh_pham5 (khánh phạm)]

Với (a / b) Mod m thì làm ntn a?

[tntxtnt]

\frac{a}{b} = a \times b^{-1} \mod m

bài toán chuyển về tính x = b^{-1} \mod m. Có x này rồi thì lấy ax \mod m là xong.

để tính x thì có nhiều cách: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation

cách 1 là xài định lý của Euler :V nếu b và m là số nguyên tố cùng nhau (coprime) thì có thể tính x = b^{\phi(m) - 1} \mod m với \phi là hàm Euler’s totient. Nếu m là số nguyên tố thì \phi(m) = m - 1, có thể tính x = b^{m-2} \mod m \enspace \text{(m prime)}.

cách 2 là tính theo Extended Euclidean algorithm. Cách này vừa kiểm tra được b và m có nguyên tố cùng nhau luôn (nếu ko coprime thì ko có x). Bên C++ có thư viện Boost.Integer họ xài cách này để tính x (mod inverse) : https://www.boost.org/doc/libs/1_77_0/boost/integer/mod_inverse.hpp, https://www.boost.org/doc/libs/1_77_0/boost/integer/extended_euclidean.hpp