【AtCoder】ABC293 E 解説【C++】

問題

コンテスト中に考えたこと・解法

はじめは愚直に求めようとしたが、ACLにあるmodint的なクラスの実装が必要だなと思い早々に見切った。
色々と考えるうちに、問題を配列長の平方根程度のサイズに区切るとできそうなことに気づく。要するに

B=1+A+A^2+...A^{\sqrt{x}-1}

を事前に計算しておけば、求める値$S$は

S = B+A^\sqrt{x}B+A^{2\sqrt{x}}B+...+A^{(\sqrt{x}-1)\sqrt{x}}B

のようにすればいけそう。ここまでで$O(\sqrt{x})$。ただしこれで求められるのは$y*y≦x$となる最大の整数$y$に対する

\sum^{y^2-1}_{i=0}A^i

なので、$y^2$～$x-1$の累乗の項は別に計算する必要がある。その計算量は一見$x$になりそうだが、少し考えると$O(\sqrt{x})$となることがわかる。

解答コード

愚直な解法でも解けるみたいです。詳しくは公式参照

int main() {
	ll a, x, m; cin >> a >> x >> m;
	ll y = sqrtl(x);
	ll ax = 1;
	rep(i, y) {
		ax = (ax * a) % m;
	}
	ll s = 0; ll cur = 1;
	rep(i, y) {
		s = (s + cur) % m;
		cur = (cur * a) % m;
	}
	ll sum = 0;
	cur = 1;
	rep(i, y) {
		ll p = (cur * s) % m;
		sum = (sum + p) % m;
		cur = (cur * ax) % m;
	}
	for (ll X = y * y; X < x; ++X) {
		sum = (sum + cur) % m;
		cur = (cur * a) % m;
	}

	cout << sum << endl;


	return 0;
}