結果

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

ソースコード

diff # 

import sys
from itertools import product

MOD = 10**9 + 7

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

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    c = list(map(int, input[1:10]))
    
    S = 0
    for i in range(1, 10):
        S += i * c[i-1]
    
    if S == 0:
        print(0)
        return
    
    factors = factorize(S)
    primes = list(factors.keys())
    exponents = []
    for p in primes:
        exponents.append(list(range(factors[p] + 1)))
    
    divisors = set()
    for exp in product(*exponents):
        d = 1
        for i in range(len(primes)):
            d *= (primes[i] ** exp[i])
        divisors.add(d)
    
    divisors = sorted(divisors, reverse=True)
    
    for d in divisors:
        has_2 = d % 2 == 0
        has_5 = d % 5 == 0
        
        valid = True
        
        if has_2:
            for i in range(1, 10):
                if c[i-1] > 0 and i % 2 != 0:
                    valid = False
                    break
            if not valid:
                continue
        
        if has_5:
            for i in range(1, 10):
                if c[i-1] > 0 and i != 5:
                    valid = False
                    break
            if not valid:
                continue
        
        print(d % MOD)
        return
    
    print(1 % MOD)

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