세 점이 모두 같은 색이라고 하자. 에서 로 가는 벡터를 , 에서 로 가는 벡터를 라 하면, 같은 색 조건에 의해 와 는 모두 짝수이다. 따라서 의 홀짝성이 같고, 의 홀짝성도 같다.
이때
이다. 위의 홀짝성 조건 때문에 는 항상 짝수이다. 가 소수이려면 이어야 한다.
이제 순서 있는 세 점 를 센 뒤 마지막에 으로 나누자. 벡터 를 고정하고, 벡터 가
를 만족하는 경우를 센다.
라 하자. 방정식 의 정수해가 존재하려면 가 를 나누어야 한다. 확장 유클리드 알고리즘으로 하나의 해 를 구하면 모든 해는
꼴이다.
각 에 대해 다음 조건을 만족해야 한다.
조건을 만족하는 각 벡터쌍 에 대해 시작점 가 놓일 수 있는 개수는 세 점 가 모두 격자 안에 들어가도록 하는 점의 개수이다. 이는 좌표와 좌표에서 각각 필요한 폭을 계산하여 얻을 수 있다.
이렇게 얻은 순서 있는 경우의 수를 모두 더한 뒤 으로 나누면 정답이다.
Solution written by GPT5.5
