結果
問題 | No.2954 Calculation of Exponentiation |
ユーザー |
|
提出日時 | 2024-11-09 02:25:32 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,302 bytes |
コンパイル時間 | 473 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 76,416 KB |
最終ジャッジ日時 | 2024-11-09 02:25:38 |
合計ジャッジ時間 | 3,687 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 4 |
ソースコード
from sys import stdin from random import randint from collections import deque, defaultdict as dd from copy import deepcopy input = stdin.readline MOD = 998244353 INF = 1 << 60 xor = randint(100, INF) def extended_gcd(a, b): if b == 0: return a, 1, 0 else: g, x, y = extended_gcd(b, a % b) return g, y, x - (a // b) * y def mod_inverse(a, m): _, x, _ = extended_gcd(a, m) return (x % m + m) % m def fast_mod_pow(x, p): res = 1 t = x z = p while z > 0: if z % 2 == 1: res = (res * t) t = (t * t) z //= 2 return res def main(): a, b = map(float, input().split()) div = 10000 a = int(a*div) b = int(b*div) g1 = extended_gcd(a, div)[0] if not (div//g1==1 and b > 0 or a//g1==1 and b < 0): print("No") return if b < 0: a = div//g1 l = 0 r = 1<<32 g2 = div//extended_gcd(b, div)[0] while l+1 < r: m = (l+r)//2 num = fast_mod_pow(m, g2) if a==num: print("Yes") return elif a < num: r = m else: l = m if fast_mod_pow(l, g2)==a or fast_mod_pow(r, g2)==a: print("Yes") else: print("No") if __name__ == "__main__": main()