結果
問題 |
No.2744 Power! or +1
|
ユーザー |
|
提出日時 | 2025-03-12 13:51:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,129 bytes |
コンパイル時間 | 465 ms |
コンパイル使用メモリ | 82,828 KB |
実行使用メモリ | 391,748 KB |
最終ジャッジ日時 | 2025-03-12 13:52:09 |
合計ジャッジ時間 | 14,174 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 TLE * 1 |
ソースコード
import heapq N,a,b,c = map(int,input().split()) C = {} x = N for i in range(2,N+1): if i*i>N:break while x%i==0: x //=i C[i] = C.get(i,0)+1 if x>1: C[x] = C.get(x,0)+1 n = 0 for p in C: n = max(n,pow(p,C[p])) K = 0 while b**K<=N*a: K += 1 A = list(range(N)) A[0] = 1 A[1] = 1 for i in range(2,N): A[i] = (A[i-1]*i)%N G = {i:[] for i in range(N+1)} for i in range(1,N): G[i].append(((i+1)%N,a)) G[N].append((0,c)) for i in range(2,N): for k in range(2,K+1): m = pow(i,k,N) G[i].append((m,pow(b,k))) k1 = 2 while pow(i,k1)<n: k1 += 1 G[i].append((N,pow(b,k1))) prod = 1 J = N-1 for i in range(2,N): prod *= i if prod>=n: J = i break for i in range(2,N): G[i].append((A[i],c)) if i>=J: G[i].append((N,c)) for i in range(n,N): G[i].append((0,c)) INFTY = 5*10**10 dist = [INFTY]*(N+1) dist[1] = 0 que = [(0,1)] while que: d,x = heapq.heappop(que) if dist[x]<d:continue for y,c in G[x]: if dist[y]>d+c: dist[y] = d+c heapq.heappush(que,(dist[y],y)) print(dist[0])