# ACL Contest 1 B - Sum is Multiple

たのしい
## 問題リンク
- https://atcoder.jp/contests/acl1/submissions/55379447

## 解法
### 準備
まず, $\displaystyle 1+2+\cdots+k=\frac{k(k+1)}{2}$ だから, 求めるべきは $\displaystyle\frac{k(k+1)}{2}$ が $N$ の倍数となるような $k$ の最小値である.

### 記号の定義

ここでひとつ記号を定義しておく.
> 定義: 正整数 $x$と素数 $p$ に対して, $v_p(x)$を $x$ を素因数分解したときの $p$ の指数とする.

たとえば $v_2(12)=v_2(2^2\times3)=2,v_3(5)=v_3(3^0\times5)=0$です.

また, この $v_p$ について以下の性質が成り立つ:
> 任意の正整数 $x,y$ に対し
> - $v_p(xy)=v_p(x)+v_p(y)$
> - $y$が $x$ を割り切るならば $\displaystyle{}v_p\left(\frac{x}{y}\right)=v_p(x)-v_p(y)$
> - $x$ が $y$ の倍数であることは, 任意の素数 $p$ に対して $v_p(x)\geq v_p(y)$ が成り立つことと同値.

### 解法

$p$ を任意の素数とする.

$v_p$ の性質を利用すると

$$v_p\left(\frac{k(k+1)}{2}\right)=v_p(k)+v_p(k+1)-v_p(2)$$

が成り立つ.

よって, $\displaystyle\frac{k(k+1)}{2}$ が $N$ の倍数となることは

$$v_p\left(\frac{k(k+1)}{2}\right)=v_p(k)+v_p(k+1)-v_p(2)\geq v_p(N)$$

すなわち

$$v_p(k)+v_p(k+1)\geq v_p(2N)$$

が任意の素数 $p$ に対して成り立つことと同値.

ここで, $k,k+1$ は常に互いに素, すなわち $1$ 以外の公約数を持たないということに着目する.

これにより, $v_p(k)\gt0$ と $v_p(k+1)\gt0$ が同時に成り立つことはないとわかる. したがって, $2N$ の素因数分解を $\prod_{i\in I}{p_i^{e_i}}$ とすると,

- $I_1\cap I_2=\emptyset$
- $I_1\cup I_2=I$

を満たす添え字集合の組 $I_1,I_2$ が存在して以下が成り立つ.

- $k$ は $\displaystyle \prod_{i\in I_1}{p_i^{e_i}}$ の倍数
- $k+1$ は $\displaystyle \prod_{i\in I_2}{p_i^{e_i}}$ の倍数

これらは

- $\displaystyle k\equiv 0\pmod{\prod_{i\in I_1}{p_i^{e_i}}}$
- $\displaystyle k\equiv -1\pmod{\prod_{i\in I_2}{p_i^{e_i}}}$

という形で言い換えることができる. したがって, $I_1,I_2$ を決定すれば, 中国剰余定理より $k$ を求めることができる.

$2N$ の素因数分解はPollardRho法などにより高速に求めることができる.
また, $(I_1,I_2)$ の選び方は $\omega$ を $2N$ の素因数の個数として $O(2^w)$ 通りあり, $\omega=O(\frac{\log N}{\log \log N})$ [らしい](https://37zigen.com/prime-complexity/#i-3)ので, $(I_1,I_2)$ は全探索することが可能.

以上よりこの問題を十分高速に解くことができた.

### 提出
- https://atcoder.jp/contests/acl1/submissions/55379447