結果

問題 No.2744 Power! or +1
ユーザー Naru820
提出日時 2025-02-11 18:10:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,074 ms / 3,000 ms
コード長 9,556 bytes
コンパイル時間 2,077 ms
コンパイル使用メモリ 172,348 KB
実行使用メモリ 16,916 KB
最終ジャッジ日時 2025-02-11 18:10:08
合計ジャッジ時間 5,678 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// 十分大きな値（ここでは 1e18）
const ll INF = 1000000000000000000LL;
 
// fast modular exponentiation: (base^exp) mod mod を返す
int modExp(int base, int exp, int mod) {
    ll result = 1;
    ll b = base % mod;
    while(exp > 0){
        if(exp & 1) result = (result * b) % mod;
        b = (b * b) % mod;
        exp >>= 1;
    }
    return (int)result;
}
 
// T0 を計算する関数
// T0 は「t! が N で割り切れる（すなわち，各素 p について
// sum_{i>=1} floor(t/p^i) >= v_p(N) となる t）の中で最小の t」
int computeT0(int N) {
    int temp = N;
    vector<pair<int,int>> factors;
    // 試し割りで N の素因数分解（N ≤ 2e5 なので十分高速）
    for (int p = 2; p*p <= temp; p++){
        if(temp % p == 0){
            int cnt = 0;
            while(temp % p == 0){
                cnt++;
                temp /= p;
            }
            factors.push_back({p, cnt});
        }
    }
    if(temp > 1) factors.push_back({temp, 1});
 
    int T0 = 1;
    // 各素因数 p^a について，最小の t を求める．
    for(auto &pr : factors){
        int p = pr.first, cnt = pr.second;
        int lo = 1, hi = N; // t は N 以下で十分
        int best = hi;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            ll sum = 0;
            ll power = p;
            while(power <= mid){
                sum += mid / power;
                if(power > mid / p) break;
                power *= p;
            }
            if(sum >= cnt){
                best = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        T0 = max(T0, best);
    }
    return T0;
}
 
// 状態の定義
// phase == 0 : 実値 X（X < T0）を状態として持つ（フェーズ1）
// phase == 1 : X の剰余 r = X mod N を状態として持つ（フェーズ2；X ≥ T0 と仮定）
struct State {
    ll cost;
    int phase; // 0: phase1, 1: phase2
    int val;   // phase1 の場合は X, phase2 の場合は r (0 <= r < N)
    bool operator>(const State &other) const {
        return cost > other.cost;
    }
};
 
// メイン
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    // 制約より N, A, B, C は 2 以上
 
    // T0 を計算：フェーズ1では X < T0 の状態を扱う
    int T0 = computeT0(N);
    // （T0 は必ず N 以下になります）
 
    // 【前処理】フェーズ1で使うために，1 ≤ x < T0 に対する x! mod N を計算
    vector<int> fact_mod(T0, 0);
    // 1-indexed で扱う（index 0 は使わない）
    fact_mod[1] = 1 % N;
    for (int i = 2; i < T0; i++){
        fact_mod[i] = (int)(((ll)fact_mod[i-1] * i) % N);
    }
    // また，x! の値が T0 未満かどうかを判定するため，
    // 実際の x! (ただし T0 未満なら正確な値，T0 以上なら T0 とする) を precompute
    vector<ll> fact_exact(T0, 0);
    fact_exact[1] = 1;
    for (int i = 2; i < T0; i++){
        // もし fact_exact[i-1] * i < T0 なら正確な値，
        // そうでなければ T0 以上とみなして T0 をセット
        if(fact_exact[i-1] > (T0 - 1LL) / i)
            fact_exact[i] = T0;
        else
            fact_exact[i] = fact_exact[i-1] * i;
    }
 
    // dp1[x]: フェーズ1 (実値状態) で X = x のときの最小コスト (1 ≤ x < T0)
    // dp2[r]: フェーズ2 (剰余状態) で X mod N = r のときの最小コスト
    vector<ll> dp1(T0, INF);
    vector<ll> dp2(N, INF);
 
    // 優先度付きキュー（Dijkstra用）
    priority_queue<State, vector<State>, greater<State>> pq;
 
    // 初期状態：X = 1 (フェーズ1)
    dp1[1] = 0;
    pq.push({0, 0, 1});
 
    while(!pq.empty()){
        State cur = pq.top();
        pq.pop();
 
        ll curCost = cur.cost;
        int phase = cur.phase;
        int curVal = cur.val;
 
        if(phase == 0){ // フェーズ1：状態 X (1 ≤ X < T0)
            if(curCost != dp1[curVal]) continue; // 更新済みなら飛ばす
 
            // 【操作1】＋1: X -> X+1 (コスト A)
            int newX = curVal + 1;
            ll newCost = curCost + A;
            if(newX < T0){
                if(newCost < dp1[newX]){
                    dp1[newX] = newCost;
                    pq.push({newCost, 0, newX});
                }
            } else {
                int r = newX % N;
                if(newCost < dp2[r]){
                    dp2[r] = newCost;
                    pq.push({newCost, 1, r});
                }
            }
 
            // 【操作2】累乗: X -> X^k, k ≥ 2, コストは B^k
            // ※ X=1 のときは 1^k = 1 なので効果がないのでスキップ
            if(curVal != 1){
                ll power = curVal;   // 現在は X^1
                ll costPow = B;      // このループで k=2 から始めるため、最初 costPow に B を掛けて B^2 とする
                for (int k = 2; ; k++){
                    costPow *= B;  // 現在 costPow = B^k
                    if(curCost > INF - costPow) break; // オーバーフロー防止
                    ll nextCost = curCost + costPow;
                    // X^k を計算する際，もし power * X < T0 ならフェーズ1内で遷移可能
                    if(power <= (T0 - 1LL) / curVal){
                        ll newVal = power * curVal;
                        if(newVal < T0){
                            if(nextCost < dp1[newVal]){
                                dp1[newVal] = nextCost;
                                pq.push({nextCost, 0, (int)newVal});
                            }
                            power = newVal; // 次の k で使う
                            if(costPow > INF / B) break;
                            continue;
                        } else {
                            // newVal >= T0 ならフェーズ2へ遷移（実際の値は捨て，剰余 mod N を記録）
                            int r = modExp(curVal, k, N);
                            if(nextCost < dp2[r]){
                                dp2[r] = nextCost;
                                pq.push({nextCost, 1, r});
                            }
                            break;
                        }
                    } else {
                        // これ以上フェーズ1内で計算できないので，フェーズ2へ
                        int r = modExp(curVal, k, N);
                        if(nextCost < dp2[r]){
                            dp2[r] = nextCost;
                            pq.push({nextCost, 1, r});
                        }
                        break;
                    }
                    if(costPow > INF / B) break;
                }
            }
 
            // 【操作3】階乗: X -> X! (コスト C)
            // 事前計算した fact_exact, fact_mod を利用する．
            ll fval = fact_exact[curVal];
            ll newCostF = curCost + C;
            if(fval < T0){
                int newX = (int) fval;
                if(newCostF < dp1[newX]){
                    dp1[newX] = newCostF;
                    pq.push({newCostF, 0, newX});
                }
            } else {
                int r = fact_mod[curVal];
                if(newCostF < dp2[r]){
                    dp2[r] = newCostF;
                    pq.push({newCostF, 1, r});
                }
            }
 
        } else { // フェーズ2：状態は剰余 r (0 ≤ r < N)，ここでは X ≥ T0 と仮定
            if(curCost != dp2[curVal]) continue;
 
            // 既に r == 0 なら X は N の倍数
            if(curVal == 0){
                cout << curCost << "\n";
                return 0;
            }
 
            // 【操作1】＋1: 剰余 r -> (r+1) mod N (コスト A)
            int new_r = (curVal + 1) % N;
            ll newCost = curCost + A;
            if(newCost < dp2[new_r]){
                dp2[new_r] = newCost;
                pq.push({newCost, 1, new_r});
            }
 
            // 【操作2】累乗: X -> X^k と同様に，剰余も r -> r^k mod N (コスト B^k)
            // ※ r=0,1 のときは変化しないので対象外
            if(curVal != 0 && curVal != 1){
                ll expCost = B; // k=2 から開始するため
                for (int k = 2; ; k++){
                    expCost *= B; // expCost = B^k
                    if(curCost > INF - expCost) break;
                    ll nextCost = curCost + expCost;
                    int r_new = modExp(curVal, k, N);
                    if(nextCost < dp2[r_new]){
                        dp2[r_new] = nextCost;
                        pq.push({nextCost, 1, r_new});
                    }
                    // 安全のため、k の上限を適当に設定
                    if(k >= 60) break;
                    if(expCost > INF / B) break;
                }
            }
 
            // 【操作3】階乗: X! (コスト C)
            // X が十分大きい（X ≥ T0）なら X! は必ず N で割り切るので，
            // 階乗操作で直接解 (剰余 0) となる
            ll nextCost = curCost + C;
            if(nextCost < dp2[0]){
                dp2[0] = nextCost;
                pq.push({nextCost, 1, 0});
            }
        }
    }
 
    // 答えは dp2[0] に入っているはず
    cout << dp2[0] << "\n";
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0