結果
問題 |
No.2744 Power! or +1
|
ユーザー |
|
提出日時 | 2025-03-12 13:56:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,179 bytes |
コンパイル時間 | 4,249 ms |
コンパイル使用メモリ | 298,136 KB |
実行使用メモリ | 213,748 KB |
最終ジャッジ日時 | 2025-03-12 13:56:14 |
合計ジャッジ時間 | 12,257 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 RE * 1 |
other | AC * 4 WA * 3 RE * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long INFTY = 5e10; long long mod_pow(long long x, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main() { int N, a, b, c; cin >> N >> a >> b >> c; map<int, int> C; int x = N; for (int i = 2; i * i <= N; ++i) { while (x % i == 0) { x /= i; C[i]++; } } if (x > 1) C[x]++; int n = 0; for (auto &[p, cnt] : C) { n = max(n, (int)pow(p, cnt)); } int K = 0; while (pow(b, K) <= (long long)N * a) K++; vector<int> A(N); A[0] = A[1] = 1; for (int i = 2; i < N; ++i) { A[i] = (A[i - 1] * i) % N; } vector<vector<pair<int, long long>>> G(N + 1); for (int i = 1; i < N; ++i) { G[i].emplace_back((i + 1) % N, a); } G[N].emplace_back(0, c); for (int i = 2; i < N; ++i) { for (int k = 2; k <= K; ++k) { int m = mod_pow(i, k, N); G[i].emplace_back(m, mod_pow(b, k, LLONG_MAX)); } int k1 = 2; while (pow(i, k1) < n) k1++; G[i].emplace_back(N, mod_pow(b, k1, LLONG_MAX)); } long long prod = 1; int J = N - 1; for (int i = 2; i < N; ++i) { prod *= i; if (prod >= n) { J = i; break; } } for (int i = 2; i < N; ++i) { G[i].emplace_back(A[i], c); if (i >= J) { G[i].emplace_back(N, c); } } for (int i = n; i < N; ++i) { G[i].emplace_back(0, c); } vector<long long> dist(N + 1, INFTY); dist[1] = 0; priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> que; que.emplace(0, 1); while (!que.empty()) { auto [d, u] = que.top(); que.pop(); if (dist[u] < d) continue; for (auto &[v, cost] : G[u]) { if (dist[v] > d + cost) { dist[v] = d + cost; que.emplace(dist[v], v); } } } cout << dist[0] << endl; return 0; }