#857519 (PyPy3) No.2264 Gear Coloring

• 問題: No.2264 Gear Coloring
• ユーザー: shobonvip
• 提出日時: 2023-04-07 22:33:08
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 165 ms / 2,000 ms
• コード長: 2,334 bytes
• コンパイル時間: 168 ms
• コンパイル使用メモリ: 82,052 KB
• 実行使用メモリ: 65,920 KB
• 最終ジャッジ日時: 2024-10-02 19:59:13
• 合計ジャッジ時間: 2,158 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 18

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n")+(not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s:self.buffer.write(s.encode("ascii"))
        self.read = lambda:self.buffer.read().decode("ascii")
        self.readline = lambda:self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda:sys.stdin.readline().rstrip("\r\n")
# バーンサイドの補題
# t ごとまわす
# let g[i] = gcd(t, A[i])
# prod_i A[i] / g[i]
# t | lcm(A)
# ok!
def makediv(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
from math import gcd
mod = 998244353
n, m = map(int,input().split())
a = list(map(int,input().split()))
lcm = 1
for i in range(n):
    lcm = lcm * a[i] // gcd(a[i], lcm)
g = makediv(lcm)
f = len(g)
dp = [0] * f
ans = 0
for i in range(f-1,-1,-1):
    r = 0
    for j in range(n):
        r += gcd(g[i], a[j])
    tmp = pow(m, r, mod)
    dp[i] = lcm // g[i]
    for j in range(i+1, f):
        if g[j] % g[i] == 0:
            dp[i] -= dp[j]
    dp[i] %= mod
    ans += dp[i] * tmp
    ans %= mod
ans *= pow(lcm, mod-2, mod)
ans %= mod
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX