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

(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?

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:

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

5 Likes
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 :cry:

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.

2 Likes
long ans = BigInteger.valueOf(a).modPow(BigInteger.valueOf(b),BigInteger.valueOf(M)).longValue();
3 Likes
  • Đặt x = a % m. Ta có ab ≡ xb (mod m)
    Bước này giảm a từ 1018 xuống x còn cỡ ~109
  • Định lý Fermat nhỏ cho biết: ap ≡ a (mod p) với a bất kì và p là số nguyên tố,
    • hay nói cách khác ap-1 ≡ 1 (mod p),
    • hay aq(p-1) ≡ 1q ≡ 1 (mod p),
    • hay aq(p-1) + r = aq(p-1)ar ≡ 1 * ar (mod p) = ar (mod p).
  • Đặt r = b % (m - 1). Ta có xb ≡ xr (mod m) với m là số nguyên tố.
    Bước này giảm b từ 1018 xuống r còn cỡ ~109

Để tính ab lẹ thì ta xài cách tính ab/2 * ab/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 a12345 = a1 + 8 + 16 + 32 + 4096 + 8192 = a1a8a16a32a4096a8192.

Để 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 2i.
Ví dụ ở đây b = (12345)10 = (11000000111001)2 có số 1 ở vị trí thứ 0, 3, 4, 5, 12, 13 từ phải qua thì tổng b = 20 + 23 + 24 + 25 + 212 + 213 = 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
}
6 Likes

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

3 Likes

Có luôn anh ơi:

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

2 Likes

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

\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 \phihà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 bm 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

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?