結果

問題 No.2954 Calculation of Exponentiation
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-11-24 19:01:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,897 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 82,892 KB
実行使用メモリ 54,056 KB
最終ジャッジ日時 2024-11-24 19:01:17
合計ジャッジ時間 2,393 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,332 KB
testcase_01 AC 34 ms
53,792 KB
testcase_02 AC 35 ms
52,696 KB
testcase_03 AC 34 ms
52,316 KB
testcase_04 AC 33 ms
52,744 KB
testcase_05 AC 33 ms
53,740 KB
testcase_06 AC 37 ms
53,264 KB
testcase_07 AC 34 ms
53,068 KB
testcase_08 AC 37 ms
52,660 KB
testcase_09 AC 37 ms
53,980 KB
testcase_10 AC 35 ms
53,796 KB
testcase_11 AC 35 ms
52,516 KB
testcase_12 AC 34 ms
53,200 KB
testcase_13 AC 36 ms
52,656 KB
testcase_14 AC 35 ms
53,276 KB
testcase_15 AC 37 ms
52,928 KB
testcase_16 AC 37 ms
53,484 KB
testcase_17 AC 36 ms
52,800 KB
testcase_18 AC 39 ms
53,144 KB
testcase_19 AC 34 ms
53,012 KB
testcase_20 AC 36 ms
52,532 KB
testcase_21 AC 36 ms
53,208 KB
testcase_22 AC 35 ms
52,884 KB
testcase_23 AC 34 ms
54,056 KB
testcase_24 AC 34 ms
52,464 KB
testcase_25 AC 35 ms
52,692 KB
testcase_26 AC 35 ms
53,448 KB
testcase_27 AC 36 ms
53,132 KB
testcase_28 AC 40 ms
53,692 KB
testcase_29 AC 39 ms
52,804 KB
testcase_30 AC 36 ms
52,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2954

import math

def calc_gcd(A, B):
    """
    正の整数A, Bの最大公約数を計算する
    """
    a = max(A, B)
    b = min(A, B)
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b


def decompose_rational(A:str):
    p, q = A.split(".")

    sign = 1
    if p.startswith("-"):
        sign = -1
        p = p[1:]

    p_ = int(p) * 10000 + int(q)
    q_ = 10000
    if p_ > 0:
        gcd = calc_gcd(p_, q_)
        return sign, p_ // gcd, q_ // gcd
    else:
        return 1, 0, 0

def primal_decompose(A):
    sqrt_a = int(math.sqrt(A))

    primes = {}
    for p in range(2, sqrt_a + 1):
        if A % p == 0:
            primes[p] = 0
            while A % p == 0:
                primes[p] += 1
                A //= p
    if A > 1:
        primes[A] = 1
    return primes


def main():
    A, B = input().split()

    _, a_p, a_q = decompose_rational(A)
    b_sign, b_p, b_q = decompose_rational(B)
    if b_p == 0:
        # 0乗は常に1
        print("Yes")
    elif b_sign == 1:
        if a_q > 1:
            print("No")
            return
        else:
            # a_pの素因数分解
            # 全ての素数の指数がb_qで割り切れるかどうか
            primes = primal_decompose(a_p)
            for v in primes.values():
                if v % b_q != 0:
                    print("No")
                    return
            print("Yes")
    else:
        if a_p > 1:
            print("No")
            return
        else:
            # a_qの素因数分解
            # 全ての素数の指数がb_pで割り切れるかどうか
            primes = primal_decompose(a_q)
            for v in primes.values():
                if v % b_q != 0:
                    print("No")
                    return
            print("Yes")





if __name__ == "__main__":
    main()
0