結果

問題 No.2264 Gear Coloring
ユーザー lam6er
提出日時 2025-03-31 17:50:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 1,764 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 71,832 KB
最終ジャッジ日時 2025-03-31 17:51:15
合計ジャッジ時間 2,309 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

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 generate_divisors_with_exponents(primes, exponents_l):
    divisors = []
    n = len(primes)
    def backtrack(index, current_exp, current_val):
        if index == n:
            divisors.append((current_val, current_exp.copy()))
            return
        p = primes[index]
        max_e = exponents_l[index]
        for e in range(max_e + 1):
            current_exp.append(e)
            backtrack(index + 1, current_exp, current_val * (p ** e))
            current_exp.pop()
    backtrack(0, [], 1)
    return divisors

n, m = map(int, input().split())
a = list(map(int, input().split()))

from math import gcd
lcm = 1
for num in a:
    g = gcd(lcm, num)
    lcm = (lcm * num) // g

if lcm == 0:
    print(0)
    exit()

factors = factorize(lcm)
primes = sorted(factors.keys())
exponents_l = [factors[p] for p in primes]

divisors = generate_divisors_with_exponents(primes, exponents_l)

total = 0
for d_value, d_exponents in divisors:
    sum_g = 0
    for num in a:
        sum_g += gcd(d_value, num)
    term = pow(m, sum_g, MOD)
    
    phi = 1
    for i in range(len(primes)):
        p = primes[i]
        e_in_l = exponents_l[i]
        e_in_d = d_exponents[i]
        e = e_in_l - e_in_d
        if e > 0:
            phi_p = ((p - 1) * pow(p, e - 1, MOD)) % MOD
            phi = (phi * phi_p) % MOD
    total = (total + term * phi) % MOD

inv_l = pow(lcm, MOD - 2, MOD)
ans = (total * inv_l) % MOD
print(ans)
0