Lũy thừa mod

Xem PDF

Điểm: 250 (p) Thời gian: 2.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Tính: \(a^{b^c}\) \(mod\) \(10^{18} + 9\).

Input

  • Dòng đầu ghi \(Q\) không quá \(5000\) - số câu hỏi.
  • \(Q\) dòng tiếp theo mỗi dòng ghi 3 số \(a,b,c\) không quá \(10^{15}\).

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

Test 1

Input
3
2 3 2
5 2 2
3 4 5
Output
512
625
824168097938645257

Bình luận


  • 1
    PhanHuyKhang    8:29 a.m. 21 Tháng 12, 2021 đã chỉnh sửa

    Tìm hiểu về định lí fermat nhỏ


    • 0
      huyhau6a2    8:42 a.m. 21 Tháng 12, 2021 đã chỉnh sửa

      hmm khó đấy mình đọc cả fermat với euler mà vẫn chả hiểu liên quan gì đến bài này hết hmm


      • 10
        NguyenPhuNhan    9:41 a.m. 21 Tháng 12, 2021

        a^(n - 1) mod n = 1
        -> a^[(n - 1).k] mod n = 1
        -> a ^ [(n - 1).k + r] mod n = a^[(n - 1).k] * a^r mod n = a^r mod n
        ->a^(b^c) mod n = a^[b^c mod (n - 1)] mod n


        • 0
          iq2000laday    4:01 p.m. 13 Tháng 6, 2024

          Bạn này đẹp trai quá cảm ơn bạn nhiều nha 🙂


          • 0
            huyhau6a2    1:11 p.m. 21 Tháng 12, 2021

            Cảm ơn bạn mình ac 600ms rồi nha


            • 0
              huyhau6a2    11:41 a.m. 21 Tháng 12, 2021 đã chỉnh sửa

              Vỗ tay vỗ tay

          7 bình luận nữa