結果

問題 No.2193 メガの下１桁
ユーザー lam6er
提出日時 2025-03-20 20:34:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,618 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 54,872 KB
最終ジャッジ日時 2025-03-20 20:36:00
合計ジャッジ時間 2,923 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

M = int(input())
D = int(input())
N = int(input())
B = int(input())

def compute_pow_mod(a, exponent, B):
    a = a % B
    if a == 0:
        return 0 if exponent != 0 else 1 % B
    if B == 2:
        return 1 % B if exponent else 0
    elif B == 3:
        exponent = exponent % 2
        return pow(a, exponent if exponent != 0 else 2, 3)
    elif B == 4:
        if a == 0:
            return 0
        elif a == 1:
            return 1
        elif a == 2:
            if exponent == 0:
                return 1 % 4
            elif exponent == 1:
                return 2
            else:
                return 0
        elif a == 3:
            exponent = exponent % 2
            return 3 ** (exponent if exponent else 2) % 4
    elif B == 5:
        exponent = exponent % 4
        exponent = exponent if exponent != 0 else 4
        return pow(a, exponent, 5)
    elif B == 6:
        if a in (1, 5):
            exponent = exponent % 2
            return a ** (exponent if exponent else 2) % 6
        elif a in (2, 4):
            if exponent == 0:
                return 1 % 6
            elif exponent == 1:
                return a % 6
            else:
                return (a ** 2) % 6
        elif a == 3:
            return 3 if exponent >= 1 else 1 % 6
        else:
            return 0
    elif B == 7:
        exponent = exponent % 6
        exponent = exponent if exponent != 0 else 6
        return pow(a, exponent, 7)
    elif B == 8:
        if a % 2 == 0:
            if a == 0:
                return 0
            elif a == 2:
                if exponent == 0:
                    return 1 % 8
                elif exponent == 1:
                    return 2
                elif exponent == 2:
                    return 4
                else:
                    return 0
            elif a == 4:
                if exponent == 0:
                    return 1 % 8
                else:
                    return 4 if exponent == 1 else 0
            elif a == 6:
                if exponent == 0:
                    return 1 % 8
                else:
                    return 6 if exponent == 1 else (6 ** 2) % 8
            else:  # a == 8 mod 8 which is 0
                return 0
        else:
            exponent = exponent % 4
            return pow(a, exponent if exponent != 0 else 4, 8)
    elif B == 9:
        if a in (1, 2, 4, 5, 7, 8):
            exponent = exponent % 6
            exponent = exponent if exponent != 0 else 6
            return pow(a, exponent, 9)
        elif a == 3 or a == 6:
            if exponent == 0:
                return 1 % 9
            elif exponent == 1:
                return a % 9
            else:
                return 0
    elif B == 10:
        if a in (1, 3, 7, 9):
            exponent = exponent % 4
            exponent = exponent if exponent != 0 else 4
            return pow(a, exponent, 10)
        elif a == 5:
            return 5
        elif a == 6:
            return 6
        elif a == 2:
            exponent = exponent % 4
            return (2 ** (exponent if exponent != 0 else 4)) % 10
        elif a == 4:
            return 4 if exponent % 2 == 1 else 6
        elif a == 8:
            exponent = exponent % 4
            return (8 ** (exponent if exponent != 0 else 4)) % 10
    elif B == 11:
        exponent = exponent % 10
        exponent = exponent if exponent != 0 else 10
        return pow(a, exponent, 11)
    else:
        return 0

def main():
    if N == 0:
        final = M % B
    else:
        current = M % B
        seen = {}
        history = [current]
        seen[current] = 0
        step = 1
        found_cycle = False
        while step <= N:
            a = (current + D) % B
            exponent = current
            next_val = compute_pow_mod(a, exponent, B)
            if next_val in seen:
                cycle_start = seen[next_val]
                cycle_length = step - cycle_start
                remaining = N - cycle_start
                if remaining < 0:
                    final = history[N]
                    break
                else:
                    mod_remaining = remaining % cycle_length
                    final = history[cycle_start + mod_remaining]
                    found_cycle = True
                    break
            else:
                seen[next_val] = step
                history.append(next_val)
                current = next_val
                step += 1
        if not found_cycle:
            final = history[-1]
    if final < 10:
        print(final)
    else:
        print('A')

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