題目大意

計算 3xmod10007

題解

使用歐拉降冪公式

ak≡{akk<φ(n)ak%φ(n)+φ(n)k≥φ(n)

對 x 取 φ(10007)=10006 的餘數即可。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    const ll mod = 10007;
    const ll phi = mod - 1; // 10007 is prime
    ll pw[2 * phi] = {1, 0};
    for (int i = 1; i < 2 * phi; ++i)
        pw[i] = 3 * pw[i - 1] % mod;

    int x;
    while (cin >> x) {
        if (x >= phi)
            x = x % phi + phi;
        cout << pw[x] << '\n';
    }
}

OJ 連結

連結：https://zerojudge.tw/ShowProblem?problemid=f372