結果

問題 No.2497 GCD of LCMs
コンテスト
ユーザー LyricalMaestro
提出日時 2024-09-21 05:39:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 512 ms / 2,000 ms
コード長 2,380 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 89,580 KB
最終ジャッジ日時 2024-09-21 05:40:02
合計ジャッジ時間 4,493 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2497

import math
from collections import deque

MOD = 998244353
MAX_INT = 10 ** 18

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u - 1, v  - 1))
    
    # 素因数分解を実施
    prime_maps = [{} for _ in range(N)]
    primes = set()
    for i in range(N):
        a = A[i]
        sqrt_a = int(math.sqrt(a))
        for p in range(2, sqrt_a + 1):
            if a % p == 0:
                prime_maps[i][p] = 0
                primes.add(p)
                while a % p == 0:
                    a //= p
                    prime_maps[i][p] += 1
        
        if a > 1:
            prime_maps[i][a] = 1
            primes.add(a)

    # 各素数に対してダイクストラで探索する
    def dijkstra(N, prime_maps, p, edges):
        next_nodes = [ [] for _ in range(2 * N)]
        for u, v in edges:
            next_nodes[u].append((v + N, 0))
            next_nodes[v].append((u + N, 0))

        value_map = {0:deque()}
        for i in range(N):
            if p in prime_maps[i]:
                next_nodes[i + N].append((i, prime_maps[i][p]))

                if prime_maps[i][p] not in value_map:
                    value_map[prime_maps[i][p]] = deque()
            else:
                next_nodes[i + N].append((i, 0))

        values = list(value_map.keys())
        values.sort()

        dists = [MAX_INT] * (2 * N)
        value_map[0].append(N)
        for k in values:
            q = value_map[k]
            while len(q) > 0:
                v = q.popleft()
                if dists[v] < MAX_INT:
                    continue
                dists[v] = k
                for w, c in next_nodes[v]:
                    if dists[w] < MAX_INT:
                        continue
                    if k < c:
                        value_map[c].append(w)
                    else:
                        q.append(w)
        return dists
    
    answers = [1] * N
    for p in primes:
        dists = dijkstra(N, prime_maps, p, edges)
        for i in range(N):
            ans = pow(p, dists[i], MOD)
            answers[i] *= ans
            answers[i] %= MOD
    
    for i in range(N):
        print(answers[i])











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