結果

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

ソースコード

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