ACL Contest 1 B - Sum is Multiple

あらすじ

解けて嬉しかったのと、解説と少し違ったのでメモです。

整数 $N$ が与えられる。 $1 + 2 + ... + k$ が $N$ の倍数になる最小の $k$ を求める。
$1 \le N\le 10^{15}$

N = 1の場合、明らかに答えは1です。
天下り的で申し訳ないのですが後々面倒なので、以降N ≧ 2として考えます。

まず

まず(整数の積) = 2N となっていることから、2Nを素因数分解するとよさそうです。

とりあえず具体例を挙げながら考えます。
ひとまず、2N = 2³ * 3² * 5² あたりにします。(N=900)
kの素因数と $k+1$ の素因数は合わせて最低でも2を3個、3を2個、5を2個持つ必要があります。

ここで重要な性質としてkとk+1は差が1なので互いに素です。
共通の因数を持たないことから例えば2を両方に割り振ることができず、2³を片方が持つ必要があります。

これを考えると(それぞれが少なくとも持つ)因数の割り振り方は

 1 vs 2^3*3^2*5^2,  2^3 vs 3^2*5^2 , ....  2^3*3^2*5^2 vs 1

で2 ^ (2Nの素因数の数) 通りになります。これらの分け方を総当たりします。

前節で考えた割り振りの各パターンについて考えます。それぞれに割り振った素因数の積をx, y と置きます。 (例: x = 2³*5², y = 3²)
ax - by = 1 となるような自然数a, bでbyが最小になるようなものを見つける必要があります。

x と y は最大公約数が1のため、 ax + by = 1となるような整数の組 (a, b) は拡張ユークリッドの互除法で求めることができます。
以下、得られたxとy の符号で場合分けをします。

(a > 0 かつ b > 0) もしくは (a < 0 かつ b < 0)
x ≧ 1, y ≧ 1 なので出現しません。 ax + by の値が 1より大きくなるか、負になるため
a > 0 かつ b < 0
求めていた条件に一致します。-byがこの分割で得られる k として最適です。条件を満たすa, b 自体は任意の自然数tに対して (a', b') = (a+ty, b-tx) でいくらでも得ることができますが、この解から得られるk' は k < k' のため最適ではありません。
a < 0 かつ b > 0
(a', b') = (a+y, b-x) で a > 0 かつ b < 0 のパターンに持っていけます。(ここ少し不安なので、間違っていたらすみません...)
a = 0 または b = 0
コーナーケースで、注意する必要があります。
x, y の分割が 1と2Nになった時に、1 * 1 + 0 * 2N = 1という解が得られますが、ここから a > 0 かつ b < 0のパターンと同じようにk = 0と持っていくのは明らかに誤りです。
分割が1と2Nの場合、k = 2N-1, k+1 = 2N とするのが最適です。 (片方が因数に2Nを持つ、差が1、積が2Nの倍数の中で最小のペア)

以上のいずれかで、分割を決めた中で最適のkを得ることができるので、これを他の分割から得られたkと比較して最小のものを出力します。