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ỏ

#1

Em có 1 bài là tính số dư của 1 số có luỹ thừa cực lớn (vd 99999 ^ 99999) cho 1 số (vd 1333 chẳng hạn), thì có thuật toán nào nhanh không ạ @@, hay các bác cho em 1 từ khoá em search gg cũng được.
liệu có quan hệ nào giữa các chữ số của luỹ thừa với số dư hay gì gì đó không ạ @@. Em cảm ơn mọi người !

#2

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

#3

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

1 Like
#4

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

#5

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

#6

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

1 Like
#7

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ứ @@@

#8

dốt.

Đọc bài này:

1 Like
#9 
#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

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