例題 P-2-3. 快速冪


提交答案

分數: 100 (部分)
時間限制: 0.6s
記憶體限制: 1G

作者:
題目類型

輸入正整數 \(x\), \(y\) 與 \(p\),計算 \(x^y \bmod p\)。\(x\), \(y\), \(p\) 皆不超過 \(10^9 + 9\)。例如 \(x=2,y=5, p=11\),則答案是\(10\)。

輸入格式

輸入 \(x\), \(y\) 與 \(p\) 在同一行,以空白間隔,行尾可能有空格。

輸出格式

輸出計算結果。

範例輸入

2 5 11

範例輸出

10

留言


  • 0
    nicole_yang0902  評論於2025年3月28日 22:35

    include <bits/stdc++.h>

    typedef long long LL; using namespace std;

    LL exp(LL x, LL y, LL p){ LL result = 1;

    while (y > 0){ if (y%2 == 1) result *= x;

    x *= x; //先平方(下一輪備用)
    y >>= 1;

    } return result % p; }

    int main(){ LL a,b,c; cin >> a >> b >> c; cout << exp(a,b,c) << endl; return 0; }


    • 0
      nicole_yang0902  評論於2025年3月28日 22:37

      等一下對不起我看錯我以為這裡是 submit 的地方