실크의 노래 (강철 영혼)

아래 풀이의 오류 등을 찾았을 경우 디스코드 0prime0으로 연락 주세요.

---

현재 체력을 $h$라고 하자. 최대한의 공격을 버틸 수 있는 전략은 다음과 같다.

• 공격을 받는다. 즉, $h \leftarrow h-A$를 수행한다.
• $h \leq A$이고 실크가 남아있다면 회복한다. 즉,
  1. $h \gt A$가 될 때까지 $h \leftarrow h + B$를 수행한다.
  2. $h \geq H$이면 $h \leftarrow H$를 수행한다.

$H \leq A$인 경우, 한 번의 공격에 즉사하므로 답은 항상 $1$이다.

$H \geq A + B$인 경우, 회복량을 항상 $B$가 되도록 할 수 있다. 따라서 답은 $\left\lceil \frac{H+BS}{A} \right\rceil$이다.

이제 $A \lt H \lt A+B$인 경우만 고려하면 된다.

회복 과정 (1)을 끝낸 후에는 항상 $A \lt h \leq A+B$가 된다는 것에 주목하자. $y=A+B-h$로 정의하면 초기값은 가 되고, 위 전략을 에 대한 식으로 쓰면 아래와 동치이다.

1. $y \leftarrow (y + A) \mod B$
2. $y \leq y_0$이면

$y \leftarrow y_0$이 수행되면 체력은 초기 상태인 최대 체력으로 돌아온다. 즉, $y = y_0$에서 시작하여 처음으로 $$로 돌아올 때까지 값의 변화는 한 주기를 형성한다. 한 주기 동안 받은 공격의 수를 라고 하면, 는 를 만족하는 최소의 양의 정수가 된다. 먼저, 다음과 같은 표기법을 정의하자.

$$(L\le x\le R)\mathrm{m}\mathrm{o}\mathrm{d}M\iff \{\begin{array}{ll}x\mathrm{m}\mathrm{o}\mathrm{d}M\in [L\mathrm{m}\mathrm{o}\mathrm{d}M,R\mathrm{m}\mathrm{o}\mathrm{d}M]& (L\mathrm{m}\mathrm{o}\mathrm{d}M\le R\mathrm{m}\mathrm{o}\mathrm{d}M)\\ x\mathrm{m}\mathrm{o}\mathrm{d}M\in [L\end{array}$$

즉, $x$는 $\left( -y_0 \leq A x \leq 0 \right) \mod B$를 만족하는 최소의 양의 정수이다. 로 쓰면, 는 를 만족하는 최소의 음이 아닌 정수이다. 이러한 문제는 에 풀 수 있음이 알려져 있으며, 예를 들어 와 같은 글에서 설명하고 있다.

$f(A, M, L, R)$을 $(L \leq A x \leq R) \mod M$을 만족하는 최소의 음이 아닌 정수 로 정의하자. 만약 이거나 이면, 이다.

만약 $2(A \mod M) > M$인 경우, 부호를 뒤집어서 $(-R \leq -A x \leq -L) \mod M$을 풀자. 즉, 이다. 그러면 을 만족하게 된다. 따라서 이제부터 항상 을 가정할 수 있다.

먼저 자명한 해가 있는지 확인하자. $(L', R') = (L, R) \mod M$으로 두자. 만약 을 만족하는 음이 아닌 정수 가 있다면, 이 해가 된다.

그렇지 않다면, $L' + Mt \leq A x \leq R' + Mt$인 가 존재하는 최소의 음이 아닌 정수 를 찾아야 한다. 이는 과 동치이고, 이를 에서 보면 를 만족하는 해를 찾는 것이다. 이렇게 를 찾았으면, 는 를 만족하는 최소의 음이 아닌 정수이다. 즉, 이다. 이 관계식으로부터 를 계산할 때 항상 을 만족하므로, 값은 배 이상 감소한다. 따라서 의 계산에는 의 시간이 소요된다.

위 방법으로 한 주기 동안 받은 공격 횟수를 계산하면 $x = 1 + f(A, B, -y_0 - A, -A)$이고, 그 동안의 회복 횟수 이다.

$S$를 $N$으로 나눈 몫을 $q$, 나머지를 $r$이라고 하자. 그러면 $q$주기를 반복하면서 $qx$번의 공격을 받고, 나머지 번의 회복은 모두 최댓값인 로 사용할 수 있다. 따라서 답은 이고, 시간 복잡도는 테스트 케이스당 이다.