結果

問題 No.2954 Calculation of Exponentiation
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-11-24 18:55:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,842 bytes
コンパイル時間 137 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 66,400 KB
最終ジャッジ日時 2024-11-24 18:55:48
合計ジャッジ時間 2,464 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,224 KB
testcase_01 AC 39 ms
52,480 KB
testcase_02 AC 34 ms
52,224 KB
testcase_03 AC 34 ms
52,224 KB
testcase_04 AC 33 ms
52,480 KB
testcase_05 AC 33 ms
52,096 KB
testcase_06 AC 35 ms
52,608 KB
testcase_07 AC 34 ms
52,480 KB
testcase_08 AC 33 ms
52,224 KB
testcase_09 AC 35 ms
52,736 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 34 ms
51,968 KB
testcase_13 AC 38 ms
52,224 KB
testcase_14 AC 33 ms
52,096 KB
testcase_15 AC 33 ms
51,968 KB
testcase_16 AC 34 ms
52,224 KB
testcase_17 AC 42 ms
52,096 KB
testcase_18 AC 34 ms
52,480 KB
testcase_19 AC 34 ms
52,352 KB
testcase_20 AC 35 ms
51,840 KB
testcase_21 AC 35 ms
52,224 KB
testcase_22 AC 35 ms
52,480 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 36 ms
52,096 KB
testcase_26 AC 34 ms
52,608 KB
testcase_27 AC 33 ms
52,224 KB
testcase_28 AC 34 ms
52,224 KB
testcase_29 AC 35 ms
52,224 KB
testcase_30 AC 34 ms
51,968 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
    gcd = calc_gcd(p_, q_)
    return sign, p_ // gcd, q_ // gcd

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_p != 0:
                    print("No")
                    return
            print("Yes")





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