結果

問題 No.181 A↑↑N mod M
コンテスト
ユーザー kimiyuki
提出日時 2016-12-27 20:02:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,001 bytes
コンパイル時間 612 ms
コンパイル使用メモリ 71,976 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-15 04:24:29
合計ジャッジ時間 1,856 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 10 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (y >= 0);
    x %= p; if (x < 0) x += p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
int solve(int a, int n, int m) {
    vector<int> tower(m);
    tower[0] = 1;
    repeat (i,m-1) tower[i+1] = powmod(a, tower[i], m);
    int x = whole(find, tower, tower.back()) - tower.begin();
    int y = tower.size() - x;
    if (n < m) {
        return tower[n];
    } else if (y == 0) {
        return tower[n % m];
    } else {
        return tower[(n - x) % y + x];
    }
}
int main() {
    int a, n, m; cin >> a >> n >> m;
    cout << solve(a % m, n, m) << endl;
    return 0;
}
0