H - Geometric Progression Editorial
by 
ryoryoryo111
平方分割による解法
\(X <= 10^{12}\)なので平方分割することを考えます。\(\sqrt{X}\) は\( 10^{6}\)程度なので、
\[ B = 1+A+A^2+...+A^{[\sqrt{X}]-1} \]
を時間内に求めることは十分できます。ここで[]はガウス記号です。 さらに\(D = A^{[\sqrt{X}]}\)として、
\[ C = B+B*D+B*D^{2}+...+B*D^{[\sqrt{x}]} \]
を求めます。これも10^6程度のstepで求めることができます。
ここで
\[ C = 1+A+A^2+...+A^{[\sqrt{X}]*[\sqrt{X}]-1} \]
です。
さて、まだ残る項が\(X-[\sqrt{X}]*[\sqrt{X}]\)ほどありますが、これは高々\(\sqrt{X}\)程度の大きさです。 \(X-[\sqrt{X}]*[\sqrt{X}]\)回、
\[ C *= A \]
\[ C += 1 \]
すると、Cは求めたいものに一致します。
例(Rust):
posted:
last update: