$x$, $y$ ($x < y$) 정점을 잇는 간선의 가중치 $w(x, y)$는 $x$, $y$의 범위가 $1 \leq x < y \leq 7500$임을 이용하면 다음과 같이 정리됩니다.

$w(x, y) = 2019201913 x + 2019201949 y \equiv -84 x -48 y \mod 2019201997 = 2019201997 - 84 x - 48 y$

구해야 하는 값은 $1$ ~ $n$ 범위의 정점을 $k$개의 집합으로 묶었을 때, 서로 다른 집합에 속하는 $x$, $y$의 $w(x, y)$ 값의 최솟값의 최댓값입니다.

최적해는 $1, 2, ..., k-1, (k, ..., n)$으로 $k$개의 집합을 구성할 때입니다. 증명은 $k \leq i \leq n$인 $i$ 중 $n$과 다른 집합에 속하는 정점이 있다면 $w(k-1, n) > w(i, n)$이라 최적해가 아니므로 최적해에서 $k \leq i \leq n$인 $i$는 모두 $n$과 같은 집합에 속하고, 이를 만족하는 배치는 유일함을 이용하면 가능합니다.

따라서 $n$, $k$에 대한 답은 항상 $w(k-1, n) = 2019201997 - 84(k-1) - 48n$입니다.

헉… 답변 정말 감사합니다!!