[codeforces] 1955G. GCD on a grid

문제 링크

$n \times m$크기의 그리드에서 오른쪽, 아래로만 이동해서 제일 왼쪽 위에서 오른쪽 아래로 이동하는데 경로가 지나가는 칸들에 적힌 값들의 GCD의 최댓값을 구하는 문제입니다.

먼저 그리드를 지나가는 모든 경로에는 $a_{1, 1}$과 $a_{n, m}$이 포함됩니다. 다시말해 GCD의 최댓값은 $\gcd(a_{1, 1}, a_{n, m})$의 약수가 됩니다.

이걸 캐치한 시점부터 문제는 간단해집니다. $a_{i, j} \leq 10^6$이므로 $\gcd(a_{1, 1}, a_{n, m})$는 많아봐야 240개의 약수를 가집니다. $(2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 720720)$ 즉, $\gcd(a_{1, 1}, a_{n, m})$의 모든 약수에 대해서 각 약수로 나누어 떨어지는 칸만을 지나가서 목적지에 도달할 수 있는지를 확인하면 $O(240nm)$에 해결할 수 있고 약수를 구하는 시간까지 포함하면 전체 시간복잡도는 $O(t\sqrt{\max(a_{i, j})} + 240\sum{nm})$이므로 충분히 시간안에 돌 수 있습니다.

추가로, 제일 큰 수 부터 시작해서 작아지는 순으로 확인하면 경로를 찾은 즉시 종료하면 되므로 평균 실행 시간이 빨라질 수 있습니다.

pseudo code는 아래와 같습니다.

t <- number of test case
loop t times {
  n, m <- sumber of row, column
  a <- n by m grid
  factors <- list of factors of gcd(a_{1, 1}, a_{n, m})
  sort factors descending order
  
  loop f in factors {
  	if path exists f divide all element in path {
    	print f
        break
    }
  }
}