結果

問題 No.181 A↑↑N mod M
コンテスト
ユーザー EmKjp
提出日時 2015-04-14 21:22:56
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,712 bytes
コンパイル時間 644 ms
コンパイル使用メモリ 85,408 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:31:21
合計ジャッジ時間 1,674 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 35 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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(A == 0) return 0;
    if(N == 0) return 1;
    if(M == 1) return 0;
    if(A == 1) return 2;
    int mmax = 20;
    int small = calcSmall(A, N - 1, mmax + 1);
    if(small <= mmax){
        return modpow(A, small, M);
    }
    int cycle = phi(M);
    ll_t sub = solve(A, N - 1, cycle);
    return modpow(A, mmax + ((sub - mmax) % cycle + cycle) % cycle, M);
}

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