結果
問題 | No.181 A↑↑N mod M |
ユーザー | yosupot |
提出日時 | 2015-04-06 00:53:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,985 bytes |
コンパイル時間 | 1,509 ms |
コンパイル使用メモリ | 168,948 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-04 03:00:19 |
合計ジャッジ時間 | 4,937 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | RE | - |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | RE | - |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,944 KB |
testcase_29 | AC | 2 ms
6,940 KB |
testcase_30 | AC | 2 ms
6,944 KB |
testcase_31 | AC | 1 ms
6,944 KB |
testcase_32 | AC | 1 ms
6,944 KB |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | RE | - |
testcase_42 | RE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; // x^n % md ll pow_mod(ll x, ll n, P md) { ll y = 1; for (int i = 0; i < n; i++) { y *= x; if (y > md.first) { y -= md.first; y %= md.second; y += md.first; } } return y; /* ll r = 1; while (n) { if (n & 1) { r = r * x; if (r > md.first) { r -= md.first; r %= md.second; r += md.first; } } x = x * x; if (x > md.first) { x -= md.first; x %= md.second; x += md.first; } n >>= 1; } return r;*/ } // x^n % md ll pow_mod(ll x, ll n, ll md) { ll r = 1; while (n) { if (n & 1) r = (r * x) % md; x = (x * x) % md; n >>= 1; } return r % md; } ll md(ll x, P m) { if (x > m.first) { x -= m.first; x %= m.second; x += m.first; } return x; } ll a; P cycle(P m) { ll x = md(1, m); map<ll, ll> mp; mp[x] = 0; for (int i = 1; i < 100000; i++) { x *= a; x = md(x, m); if (mp.count(x)) { return {mp[x], i-mp[x]}; } mp[x] = i; } assert(false); } ll solve(ll n, P m) { if (n == 0) { return md(1, m); } P mm = cycle(m); return pow_mod(a, solve(n-1, mm), m); } int main() { ll n, M; cin >> a >> n >> M; assert(1 <= a && a <= 1e9); assert(0 <= n && n <= 1e9); if (a == 1 || n == 0) { cout << 1 % M << endl; return 0; } if (M == 1) { cout << 0 << endl; return 0; } P p = cycle(P(0, M)); if (n < 10000) { cout << pow_mod(a, solve(n-1, p), P(0, M)) << endl; return 0; } assert(false); map<ll, ll> mp; return 0; }