結果

問題 No.181 A↑↑N mod M
ユーザー EmKjpEmKjp
提出日時 2015-04-14 13:03:11
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,676 bytes
コンパイル時間 700 ms
コンパイル使用メモリ 86,140 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-04 14:26:01
合計ジャッジ時間 1,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 1 ms
6,944 KB
testcase_27 AC 1 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 1 ms
6,944 KB
testcase_31 WA -
testcase_32 AC 1 ms
6,940 KB
testcase_33 AC 1 ms
6,940 KB
testcase_34 AC 1 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 1 ms
6,940 KB
testcase_37 AC 2 ms
6,944 KB
testcase_38 AC 2 ms
6,940 KB
testcase_39 AC 2 ms
6,940 KB
testcase_40 AC 2 ms
6,940 KB
testcase_41 AC 2 ms
6,940 KB
testcase_42 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll_t;


ll_t modpow(ll_t x , ll_t y , ll_t mod){
    x %= mod;
  
    ll_t t = x, res = 1;
    for(; y ; y >>= 1){
        if(y & 1) {
            res = res * t;
            if(res >= mod) res %= mod;
        }
        t = t * t;
        if(t >= mod) t %= mod;
    }
    return res;
}


vector<ll_t> g_prime;
const int MAX_PRIME=5000;
bool is_prime_[(MAX_PRIME+1)/2] ; 

bool is_prime(ll_t x){
    if(x==2) return true;
    if(x<=1 || x%2==0) return false;
    return is_prime_[x/2];
}

void setup_prime()
{
    fill_n(is_prime_ , (MAX_PRIME+1)/2 , true);
    g_prime.clear() ; 
    g_prime.push_back(2);
    for(int i=3;i<=MAX_PRIME;i+=2){
        if(!is_prime_[i>>1]) continue;
        g_prime.push_back(i); 
        for(int j=i+i+i;j<=MAX_PRIME;j+=i+i){
            is_prime_[j>>1]=false;
        }
    }
}

int MaxPower = 5000;

ll_t calcSmall(ll_t A, ll_t N, ll_t limit){
    if(A == 0) return 0;
    if(A == 1) return 1;
    if(N == 1) return min(A, limit);
    if(N == 2){ // A ^ A
        if(A <= 10) return min(modpow(A, A, 1LL<<60), limit);
    }
    if(N == 3){ // A ^ (A ^ A)
        if(A == 2) return min(limit, 1LL<<16);
    }
    return limit;
}


ll_t phi(ll_t x){
    ll_t val = x;
    for(int i=0;i<(int)g_prime.size();i++){
        if(g_prime[i] > x) break;
        if(x % g_prime[i] == 0){      
            val = val / g_prime[i] * (g_prime[i] - 1) ;
            while(x % g_prime[i] == 0)
                x /= g_prime[i];
        }
    }
    if(x>1){
        val = val / x * (x - 1) ; 
    }
    return val;
}

// A^A^A .. (x n) % mod
ll_t solve(ll_t A, ll_t N, ll_t M){
    if(N == 0) return 1;
    if(M == 1) return 0;
    if(A == 0) return 0;
    if(A == 1) return 1;
    int mmax = 1000;
    int small = calcSmall(A, N - 1, mmax + 1);
    if(small <= mmax){
        return modpow(A, small, M);
    }
    int cycle = phi(M);
    return modpow(A, mmax + (solve(A, N - 1, cycle) - mmax) % cycle, M);
}

int main()
{
    setup_prime();
    int A,N,M;
    cin>>A>>N>>M;
    cout<<solve(A, N, M) % M<<endl;
    return 0;
}
0