라 하자. 세기 인 입자 하나는 총 를 더하므로 인 후보만 확인한다.
를 번 오비탈에 넣은 입자 수라 하고 인덱스를 에서 순환시킨다. 를 계산하면 이다. 개의 순환을 각각 길이 의 수열로 펼친다. 차분을 한 번 적분하고 순환 조건으로 초기 기울기를 정한 뒤 다시 적분한다. 순환마다 기본 해에 상수를 더하는 자유도가 남는다.
기본 해 전체의 합을 , 각 순환의 최솟값의 부호를 바꾸어 더한 값을 이라 하자. 필요한 입자 수는 이다. 가 의 배수이고 일 때 가능하다.
후보 수를 라 하면 시간 복잡도는 , 공간 복잡도는 이다.
증명
삼각형 커널의 이차 차분은 중앙에 , 양쪽으로 칸 떨어진 곳에 만 남긴다. 한 순환에서 라 두면 이다. 이어야 기울기가 순환하고, 이 초기 기울기를 유일하게 결정한다. 정수 기울기가 존재하지 않으면 불가능하다.
서브태스크 1에서는 입자의 세기가 최댓값 보다 클 수 없으므로 세 후보만 확인한다.
서브태스크 2에서 공차를 라 하자. 이면 이 의 배수인지 확인한다. 이면 이어야 한다. , 라 두면 기본 해의 합은 이고, 최소 비음수 해의 합은 이다. 따라서 및 만 확인하여 후보 하나를 에 처리한다.
두 번째 적분으로 얻는 정수 해는 같은 순환에 상수를 더하는 것 외에는 유일하다. 그 상수는 기본 해의 최솟값의 부호를 바꾼 값 이상이어야 하고, 입자 수를 배만큼 증가시킨다. 따라서 제시한 합동 조건과 하한이 비음수 정수 해의 필요충분조건이다. 이 해가 만드는 세기와 는 이차 차분과 합이 같다. 원 위에서 이차 차분이 인 수열은 상수이므로 두 세기는 같다.
등차수열의 공차가 이면 , 만 이 아니다. 두 위치가 서로 다른 순환에 속하면 각 순환의 의 합이 일 수 없으므로 이어야 한다. 위치 에서 출발하여 씩 이동할 때 위치 은 번째에 나타난다. 이 순환의 기본 해는 높이 인 두 선형 구간으로 이루어져 합이 이고 최솟값은 이다. 따라서 최소 비음수 해의 합이 이며, 상수를 더해 늘릴 수 있는 합은 의 배수이다. 이면 모든 순환의 기본 해가 이므로 필요한 조건은 , 즉 이다.
Solution written by GPT6
