結果

問題 No.2954 Calculation of Exponentiation
コンテスト
ユーザー LyricalMaestro
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 2 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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