結果
問題 |
No.1648 Sum of Powers
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:06:54 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,838 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 82,792 KB |
実行使用メモリ | 101,456 KB |
最終ジャッジ日時 | 2025-06-12 14:07:37 |
合計ジャッジ時間 | 9,535 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 WA * 27 |
ソースコード
MOD = 998244353 def main(): import sys A, B, P, Q = map(int, sys.stdin.readline().split()) if B == 0: if A == 0: if P == 0 and Q == 0: print(2) else: pass return else: if Q == 0: if P == 0: print(2) else: pass return inv_Q = pow(Q, MOD-2, MOD) expected_A = (P * inv_Q) % MOD if expected_A != A: return X = A C = Q if X == 0: if C == 0: print(1000000000000000000) else: pass return m = int(1e5) table = {} current = 1 for j in range(m): if current not in table: table[current] = j current = (current * X) % MOD X_inv_m = pow(X, m * (MOD-2), MOD) giant = C found = False for i in range(m+1): if giant in table: k = i * m + table[giant] N = k + 1 if N >= 2 and N <= 1e18: print(N) found = True break giant = (giant * X_inv_m) % MOD if not found: print(1000000000000000000) return else: inv_B = pow(B, MOD-2, MOD) m = 10**5 forward = {} s_prev, s_curr = 2, A forward[(s_prev, s_curr)] = 0 prev_pair = None for n in range(1, m+1): s_next = (A * s_curr - B * s_prev) % MOD new_s_prev, new_s_curr = s_curr, s_next current_pair = (new_s_prev, new_s_curr) if current_pair == (s_prev, s_curr): if new_s_prev == new_s_curr and new_s_prev == s_prev: print(1000000000000000000) return if current_pair not in forward: forward[current_pair] = n s_prev, s_curr = new_s_prev, new_s_curr prev_pair = current_pair current_s_prev, current_s_curr = Q, P for t in range(m+1): current_pair = (current_s_prev, current_s_curr) if current_pair in forward: k = forward[current_pair] N = k + t + 1 if 2 <= N <= 10**18: print(N) return s_prev_prev = (A * current_s_prev - current_s_curr) * inv_B % MOD current_s_prev, current_s_curr = s_prev_prev, current_s_prev print(1000000000000000000) return if __name__ == "__main__": main()