結果

問題 No.1632 Sorting Integers (GCD of M)
ユーザー gew1fw
提出日時 2025-06-12 15:45:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,617 bytes
コンパイル時間 473 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 59,136 KB
最終ジャッジ日時 2025-06-12 15:45:10
合計ジャッジ時間 4,330 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other WA * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n //= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n //= i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def get_divisors(factors):
    divisors = [1]
    for p, cnt in factors.items():
        current_length = len(divisors)
        for e in range(1, cnt + 1):
            p_power = p ** e
            for i in range(current_length):
                divisors.append(divisors[i] * p_power)
    divisors = list(set(divisors))
    divisors.sort(reverse=True)
    return divisors

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    c = list(map(int, input[1:10]))
    
    sum_digits = 0
    for i in range(9):
        sum_digits += (i + 1) * c[i]
    
    if sum_digits == 0:
        print(0)
        return
    
    factors_S = factorize(sum_digits)
    divisors = get_divisors(factors_S)
    
    MOD = 10**9 + 7
    for d in divisors:
        if d == 0:
            continue
        factors_d = factorize(d)
        has2 = False
        has5 = False
        for p in factors_d:
            if p == 2:
                has2 = True
            elif p == 5:
                has5 = True
        
        if has2:
            sum_odd = c[0] + c[2] + c[4] + c[6] + c[8]
            if sum_odd != 0:
                continue
        if has5:
            if c[4] != N:
                continue
        
        print(d % MOD)
        return

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