Hỏi về thuật toán lấy số dư của phép chia một lũy thừa cho 1 số nhỏ

Bạn đọc 2 bài trong link này:

GitHub

drgnz/diễn đànWiki

diễn đànWiki - Dạy Nhau Học Wiki cho thành viên mới

a^b%x=(a%x)^b % x
(axb)%x=(a%x)x(b%x) % x

em học hơi giốt toán, nếu áp dụng cái trên vẫn ra số rất lớn ví dụ vẫn ra là (5^9999 %x) thì áp dụng cái công thức thứ 2 phân tích kiểu gì ạ @@ đội hơn bác !!1

ko chia nhỏ cơ số ra đc nữa thì chia nhỏ lũy thừa thôi :3

Lũy thừa có cách riêng mà đổi số mũ ra nhị phân rồi nhìn theo đó nhân vào.

chuyển luỹ thừa sang nhị phân ạ ? sau đó tính kiểu gì, em không biết cái cách ấy mới hỏi các bác chứ @@@

giốt

dốt.

sau đó tính kiểu gì

Đọc bài này:

Giờ rảnh được chút, làm thêm một bài nữa về một thuật toán cơ bản: tính lũy thừa an bằng phương pháp chia để trị. Chắc mọi người đa số hay dùng vòng lặp nhỉ (cứ ừ đại đi), bây giờ đổi gió xíu nhé Vào luôn vấn đề, như mọi người đã biết, an được tính bằng cách nhân n lần số a (nói vậy cho gọn đi) Mình lấy ví dụ: a8 = a . a . a . a . a . a . a . a (8 chữ a lận nhé) Ta nhận thấy rằng có thể chia nửa cái phép tính trên kia ra, như thế này: a8 = a4 + 4 = a4 . a4 trong đó, a4 có thể được tí…

#include <iostream>
#include <cstdint>

// Calculate (a * b) mod m
int32_t modmul(int32_t a, int32_t b, int32_t m)
{
    return static_cast<int32_t>(static_cast<int64_t>(a) * b % m);
}

// Calculate (a ^ e) mod m
int32_t modpow(int32_t a, int32_t e, int32_t m)
{
    int32_t ret = e % 2 ? a : 1;
    while (e >>= 1)
    {
        a = modmul(a, a, m);
        if (e % 2) ret = modmul(ret, a, m);
    }
    return ret;
}

int main()
{
    std::cout << modpow(99999, 99999, 1333);
}

khỏi đệ quy

32_t 64_t nhức mắt quá thì cứ phang int với long long cũng tạm được