GCD Escape

解説

非負整数 $x$ に対して、$f(x)$ を

$$f(x)=\gcd(x,M)$$

と定義する。

操作では $x$ が減少し、かつ $f(x)$ の値が変わる必要がある。

ここで、$KM,KM-1,\ldots,0$ の順に $f(x)$ を考える。

$f(x)$ の値が変わらない範囲では、高々 $1$ 個までしか選ぶことができない。また、$f(x)$ の値が変わるたびに、その範囲の最小の整数を選べば常に操作できる。

よって答えは、$1\le x\le KM$ のうち

$$f(x)\ne f(x-1)$$

となる $x$ の個数である。

連続する $2$ 整数は互いに素なので、

$$f(x)=f(x-1)\iff f(x)=f(x-1)=1$$

が成り立つ。

また、$f(x)$ は周期 $M$ である。したがって、$1\le x\le M$ において $f(x)=f(x-1)=1$ を満たす $x$ の個数を $C$ とすると、答えは

$$K(M-C)$$

となる。

$M$ を素因数分解して

$$M=\prod_{i=1}^{r}p_i^{e_i}$$

とする。

$f(x)=f(x-1)=1$ となるための必要十分条件は、すべての $i$ について

$$x\not\equiv 0,1\pmod{p_i}$$

となることである。

$p_i^{e_i}$ を法としたとき、この条件を満たす余りは $p_i^{e_i-1}(p_i-2)$ 個ある。

よって、各素因数について考えることで、

$$C=\prod_{i=1}^{r}p_i^{e_i-1}(p_i-2)$$

となる。ただし、$M=1$ の場合は $C=1$ となる。

以上より、試し割りを用いることで、 $O(\sqrt M)$ でこの問題を解くことができる。