結果
| 問題 |
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 |
ソースコード
#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;
}