AtCoder Regular Contest #004 C. 平均値太郎の憂鬱

問題

1からNまでの値の平均値を計算する際、ある整数Mだけを足し忘れてしまった。
間違った平均値のみわかっている場合、元のN、Mでありうるものを列挙する。

既約分数とは限らない分数「X/Y」が与えられ、それぞれ1<=X<=10^18,1<=Y<=10^9,0

考え方

与えられるX,Yは既約にするため、gcd(X,Y)で割っておく。

元のNはYの倍数であるはずなので、N=a*Yと書ける。なので、間違った平均値の値はa*Xとなる。(割ったらX/Yにならないといけないため)

なので、MがNを超えるような結果になるまでaを順番に確認していけばよい、、、

しかし、1から確認していくと無駄が多いため、aがどの程度の値になるかを考える。

Mは1〜Nまでありうる。したがって、間違った平均値a*Xは、
(1〜Nの総和)-N <= a*X < (1〜Nの総和)
の不等式が成り立つ。
(1〜Nの総和)=N(N+1)/2で、N=a*Yなので、aが1以上の整数としてaについて解くと、
a > 2X/Y^2 - 1/Y
a <= 2X/Y^2 + 1/Y
となる。
したがって、2X/Y^2 <= a <= 2X/Y^2 + 1の範囲で確認すればよい。(aは高々2回の確認で済むので計算時間は大丈夫)

次に桁溢れを考えたいので、NおよびMの値がどの程度まで大きくなるかを考える。
上記の式より、N = a*Y <= 2X/Y + 1だが、問題文よりX/Y<=10^9が保障されている。
なので、(1〜Nの総和)は2*10^18+3*10^9+1まででsigned64bit整数に収まる。