8月何もしてなくてやべ〜。
August Cook-Off 2021 Division 1 - C2C
分割統治法。
左右の区間いずれかに最大値の上位2個が固まってる場合は、尺取りしながら累積maxを更新することで処理できる。
左右に跨ってる場合は、スライド最小値の要領で処理できる。
最大値上位2個の位置関係を決めうった実装をするようにすると、数列Reverseして2回解けば良いので実装量を減らすことが可能。
技術室奥プログラミングコンテスト#6 Day1
upsolve の続き。
I. 1<->k
解説に倣って $ N $ に対する本問題の答えを $ f(N) $ とおく。
この時互いに素な自然数 $a , b$ に対して、$f(ab) = f(a)f(b)$ が成立する。
この証明には、
$$ \begin{align} &x ^ {2} \equiv 1 \pmod {ab} \\ \Leftrightarrow \, &x ^ {2} \equiv 1 \pmod{a} \land x ^ {2} \equiv 1 \pmod{b} \\ \Leftrightarrow \, &(x \% a) ^ {2} \equiv 1 \pmod{a} \land (x \% b) ^ {2} \equiv 1 \pmod{b} \end{align} $$
が成立することを利用する。1つ目の $\Leftarrow$ は、中国剰余定理より一意性があるから成り立つ。
素数毎に独立に考えられることが分かったので、奇素数の場合と2の場合に分けて考える。
- 奇素数の場合
$$ x ^ {2} \equiv 1 \pmod {p ^ {e}} \Leftrightarrow (x + 1)(x - 1) \equiv 0 \pmod {p ^ {e}}$$
であり、$p \geq 3$ であることに留意すると、条件を満たすのは常に $x = 1, -1$ の2つである。
- 2の場合
同様に $(x + 1)(x - 1) \equiv 0 \pmod {2 ^ {e}}$ を考える。
$e = 1$ の場合、条件を満たすのは $x = 1$ の1通り。
$e = 2$ の場合、条件を満たすのは $x = 1, 3$ の2通り。
$3 \leq e$ の場合、条件を満たすのは $x = \pm 1 , 2^{e-1} \pm 1$ の4通り。
これで全ての場合が網羅出来ていて、クエリ毎に $O(\sqrt{N})$ で解くことができる。
