結果

問題 No.25 有限小数
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:40:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 1,538 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 54,324 KB
最終ジャッジ日時 2025-03-20 20:40:25
合計ジャッジ時間 2,221 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def finite_decimal_last_digit():
    N = int(input())
    M = int(input())
    
    gcd_val = math.gcd(N, M)
    n = N // gcd_val
    m = M // gcd_val
    
    # Check if denominator has only 2 and 5 as factors
    def factorize_denominator(d):
        x = 0
        while d % 2 == 0:
            x += 1
            d = d // 2
        y = 0
        while d % 5 == 0:
            y += 1
            d = d //5
        return (x, y, d)
    
    denom_2, denom_5, remainder = factorize_denominator(m)
    if remainder != 1:
        print(-1)
        return
    
    # Factorize numerator n into 2^a2 * 5^a5 * m_part
    a2 = 0
    while n % 2 == 0:
        a2 += 1
        n = n // 2
    a5 = 0
    while n % 5 == 0:
        a5 += 1
        n = n //5
    m_prime_last = n % 10
    
    k = max(denom_2, denom_5)
    total_2 = a2 + (k - denom_2)
    total_5 = a5 + (k - denom_5)
    delta = total_2 - total_5
    
    if delta < 0:
        print(5)
    elif delta == 0:
        print(m_prime_last % 10)
    else:
        # Determine the last digit based on m_prime_last and delta
        key = m_prime_last % 10
        if key not in {1, 3, 7, 9}:
            print(-1)  # should never happen due to prior factorization
            return
        # Mapping for each possible key and delta modulo 4
        table = {
            1: [2, 4, 8, 6],
            3: [6, 2, 4, 8],
            7: [4, 8, 6, 2],
            9: [8, 6, 2, 4]
        }
        r = (delta - 1) % 4
        print(table[key][r])
    
finite_decimal_last_digit()
0