좋은 삼각형

세 점이 모두 같은 색이라고 하자. $A$에서 $B$로 가는 벡터를 $(a,b)$, $A$에서 $C$로 가는 벡터를 $(c,d)$라 하면, 같은 색 조건에 의해 $a+b$와 $c+d$는 모두 짝수이다. 따라서 $a,b$의 홀짝성이 같고, $c,d$의 홀짝성도 같다.

이때

$$W=|ad-bc|$$

이다. 위의 홀짝성 조건 때문에 $ad-bc$는 항상 짝수이다. $W$가 소수이려면 $W=2$이어야 한다.

이제 순서 있는 세 점 $(A,B,C)$를 센 뒤 마지막에 $6$으로 나누자. 벡터 $u=(a,b)$를 고정하고, 벡터 $v=(c,d)$가

$$ad-bc=\pm 2$$

를 만족하는 경우를 센다.

$g=\gcd(a,b)$라 하자. 방정식 $ad-bc=\pm 2$의 정수해가 존재하려면 $g$가 를 나누어야 한다. 확장 유클리드 알고리즘으로 하나의 해 를 구하면 모든 해는

$$(c,d)=\left(c_0+\frac{a}{g}t,\ d_0+\frac{b}{g}t\right)$$

꼴이다.

각 $t$에 대해 다음 조건을 만족해야 한다.

• $c$와 $d$가 격자 안에서 가능한 벡터 범위에 들어간다.
• $c+d$가 짝수이다.

조건을 만족하는 각 벡터쌍 $(u,v)$에 대해 시작점 $A$가 놓일 수 있는 개수는 세 점 $A,A+u,A+v$가 모두 격자 안에 들어가도록 하는 점의 개수이다. 이는 $x$좌표와 좌표에서 각각 필요한 폭을 계산하여 얻을 수 있다.

이렇게 얻은 순서 있는 경우의 수를 모두 더한 뒤 $6$으로 나누면 정답이다.

Solution written by GPT5.5