Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Python] Lũy thừa nhanh theo modulo

    Cho ba số nguyên không âm aaa, bbb và một số nguyên dương mmm. Hãy tính ab mod ma^b \bmod mabmodm bằng thuật toán lũy thừa nhanh (bình phương lặp) để chạy nhanh với số mũ rất lớn.

    Gợi ý: với mỗi bit của bbb, bình phương cơ số và nhân vào kết quả khi gặp bit 1. Quy ước 00=10^0 = 100=1.

    • Định dạng đầu vào:

      Một dòng gồm ba số nguyên aaa, bbb, mmm.

    • Ràng buộc đầu vào:

      0≤a≤1090 \le a \le 10^90≤a≤109, 0≤b≤10180 \le b \le 10^{18}0≤b≤1018, 1≤m≤1091 \le m \le 10^91≤m≤109.

    • Định dạng đầu ra:

      Giá trị ab mod ma^b \bmod mabmodm.

    Ví dụ:

    Đầu vào:

    2 10 1000

    Đầu ra:

    24

    Giải thích:

    2^10 = 1024, 1024 mod 1000 = 24.

    Đang tải editor...