题解
- 타일의 가로 길이는 xL (1≤x≤N) 꼴입니다. 가로 길이가 xL이면 세로 길이는 xL 이하이면서 xL과 서로소인 양의 정수이므로 φ(xL)가지입니다.
- 따라서 ∑x=1Nφ(xL)을 구하면 됩니다.
- g=gcd(x,L)이라 하면 φ(xL)=φ(x)φ(입니다.
- N≤107이므로 φ(1),…,φ(N)을 에라토스테네스의 체로 배열에 미리 구해 둡니다. 이라 도 이 배열에서 꺼내면 됩니다.
- φ(x)⋅φ(g)g=은 정수이므로, 를 로 나눈 값을 정수로 바로 계산할 수 있습니다. 모듈러 역원은 필요 없습니다. 이므로 64비트 정수로 충분합니다.
- 이 값들을 더한 뒤 φ(L)을 곱하고 998244353으로 나눈 나머지를 출력합니다. φ(L)은 L을 까지 나눠 보며 소인수분해해 구합니다.
- 시간복잡도는 O(L+NloglogN+입니다.
L
)
φ(g)g
g
≤
x≤
N
φ(L)φ(xL)
φ(x)⋅g φ(x)⋅g≤1014
N
log
L
)
