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

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/diễn đànWiki/blob/master/Algorithm/Math/Modulo/modulo.md

Chào mừng các bạn đến với mục Algorithm của diễn đànWiki.

Hôm nay mình sẽ giới thiệu với các bạn một số phép toán liên quan đến số dư.

# Khởi đầu
Sẽ có rất nhiều bài toán yêu cầu tính toán với modulo 10^9+7, 10^6+9,... Có thể đây chỉ là vấn đề của Toán, nhưng đối với nhiều bạn không giỏi Toán cho lắm thì đây là một vấn đề lớn.

# Khái niệm
Có 2 số nguyên a, b và một số nguyên n khác 0. Ta định nghĩa `a đồng dư với b` khi a và b có cùng số dư khi chia cho n.

Kí hiệu `a ≡ b (mod n)`

# Tính chất
* Tính phản xạ: `a ≡ a (mod n)`
* Tính đối xứng: `a ≡ b (mod n) <=> b ≡ a (mod n)`
* Tính chất bắc cầu: Nếu `a ≡ b (mod n)` và `b ≡ c (mod n)` thì `a ≡ c (mod n)`

* Nếu `a ≡ b (mod n)` thì:
	- `a + k ≡ b + k (mod n)` với mọi số nguyên k
	- `k * a ≡ k * b (mod n)` với mọi số nguyên k

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

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.

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

• Đặ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
}

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

Có luôn anh ơi:

GeeksforGeeks – 11 Nov 15

BigInteger Class in Java - GeeksforGeeks

BigInteger class is used for mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types. For… Read More »

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