ABC186/E - Throne

문제.

자연수 N, S, K가 부여됩니다.
다음 조건을 충족시키는 최소 자연수 m가 있는지 판정하면 대답한다.
S + mK = 0\bmod N
그러나 N은 10^9 정도, O(N) 이하로 계산하십시오.

해법

공식적으로 상호 제법으로 해결된 것이다.
지금 여기에 쓰실 건요.
그게 다야.

정답은 N 이하입니다.

a_m = (S+mK)\modN의 수열
a_0, a_1,\ldots
문제를 사고하다.
문제는 이것이 처음으로 거스름돈을 찾는 것이다.
하면, 만약, 만약...i = a_하면, 만약, 만약...{i+1} = a_{j+1}으로 바뀌면 이 몇 열의 값이 순환하는 것을 알 수 있다.
그리고 얻을 수 있는 값은 N개의 자연수 중 하나이기 때문에 비둘기의 둥지 원리를 응용하여0~aN을 고려하면 반드시 중복을 포함해야 한다.
따라서 제로가 있는 항목은 반드시 그 안에 포함된다.

Baby-Step Giant-Step

자연수 m는 현재 0 이상 N 이하로 한정되어 있지만, 이것은 작은 것부터 순서대로 이하의 합으로 분해할 수 있다.

0\sqrt{N} + 0

0\sqrt{N} + 1

0\sqrt{N} + 2

\vdots

0\sqrt{N} +\sqrt{N},

1\sqrt{N} + 0

1\sqrt{N} + 1

1\sqrt{N} + 2

\vdots

1\sqrt{N} +\sqrt{N},

\vdots

(\sqrt{N}-1)\sqrt{N} + 0

(\sqrt{N}-1)\sqrt{N} + 1

(\sqrt{N}-1)\sqrt{N} + 2

\vdots

(\sqrt{N}-1)\sqrt{N} +\sqrt{N}.

그러나 여기\sqrt{m}는 자연수 범위의 제곱근으로 k^2\geqm의 최소 자연수 k를 충족시킨다.
위의 공식을 자세히 보면 중복이 포함되어 있지만 작은 순서를 망라하여 조사하는 것이 중요하기 때문에 이러쿵저러쿵 말할 필요가 없다.
그러면 조사(S+mK)\bmod N=0을 사용하려면 (i\sqrt{N}+j)를 사용하십시오.
(S + i\sqrt{N} K + j K)\bmod N = 0
알아보면 돼.
위조 코드로 쓰면

r = sqrt(m);
for i in range(0, r) {
  for j in range(0, r) {
    if (S + i * r * K + j * K) % N == 0 {
      yield i * r + j;
    }
  }
}

이 범위는 양쪽을 포함한다.
이 두 순환을 그대로 실행하면 결과는 O(N)이지만 range에 대한 사전 정리는 다음과 같다.

d = {}  // set
for j in range(0, r) {
  d.insert((j * K) % N);
}

그렇다면 각j에 대해
S + i\sqrt{N} K + x = 0\mod N
조건을 만족하는 x재i에게 물어봐도 될까요?
어쨌든mod를 찾으려면 dmod의 값을 미리 찾는 것이 가장 좋다.
공식 변형,
x = (-S - i\sqrt{N} K)\bmod N
이렇게 하면 돼요. 이게 d에 포함되는지 보면 돼요.d 산 목록이나 이분 탐색 트리로 이곳을 유지하면 고속으로 갈 수 있다.
또한 현재 문제가 된 것은 존재 여부뿐만 아니라 존재할 때의 추가 글자 m도 필요하다.d 하나의 집합이 아니라 그 값을 실현할 때까지 보존하는 것이 좋다.
HashMap, BTreMap, 그런 사전으로 썼어요.

d = {}  // dict
for j in range(0, r) {
  x = (j * K) % N;
  if x not in d {
    d[x] = j;
  }
}

d는 만족(jK)\bmodN의 최소 자연수 j를 나타낸다.

for i in range(0, r) {
  y = (S + i * r * K) % N;
  x = N - y;  // y + x = 0 を満たす x
  if x in d {
    m = i * r + d[x];
    print(m);
    return;
  }
}

// 見つからなかった
print(-1);

이렇게 되면 O(\sqrt{N}) 정도i의 상담 시간이 여기에 걸린다).