結果

問題 No.434 占い
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:23:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 1,471 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 87,388 KB
最終ジャッジ日時 2025-04-24 12:25:29
合計ジャッジ時間 3,933 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_factors_of_3(x):
    count = 0
    while x % 3 == 0 and x != 0:
        count += 1
        x = x // 3
    return count

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    for s in cases:
        n = len(s)
        sum_mod = 0
        current_val = 1  # C(n-1, 0) starts as 1
        current_exp = 0
        for i in range(n):
            if i == 0:
                c = (current_val * (3 ** current_exp)) % 9
            else:
                numerator = (n - i)
                denominator = i
                num_3 = count_factors_of_3(numerator)
                den_3 = count_factors_of_3(denominator)
                current_exp += (num_3 - den_3)
                numerator_red = numerator // (3 ** num_3)
                denominator_red = denominator // (3 ** den_3)
                inv_denominator_red = pow(denominator_red, -1, 9)
                current_val = (current_val * numerator_red) % 9
                current_val = (current_val * inv_denominator_red) % 9
                if current_exp >= 2:
                    c = 0
                else:
                    c = (current_val * (3 ** current_exp)) % 9
            digit = int(s[i])
            sum_mod = (sum_mod + digit * c) % 9
        if sum_mod == 0:
            has_non_zero = any(c != '0' for c in s)
            print(9 if has_non_zero else 0)
        else:
            print(sum_mod)

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