これ好き!楽しい!!
問題概要
長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである:
- を % で置き換える
個の整数 それぞれに対して ステップの操作を行って得られる結果を答えよ。
制約
考えたこと
愚直にやると となって間に合わない。工夫が必要になる。ここで注目したいことは、たとえば で割ったあとに、 で割っても値は変わらない。一般に、 であるとき、
- % は最初から 未満なので、% をしても値は変化しない
ということになる。よって、数列 において、 () となっている部分はあらかじめ削除することができる。よって数列 は単調減少であるものと考えてよい!!
そうとわかれば二分探索
そうとわかれば、数列 による操作を効率化できる。具体的には、たとえば に対して を適用するとき
- まず 28 % 10 = 8 となる
- 数列 A において、最初に 8 以下となる箇所を探す (5)
- 8 % 5 = 3 となる
- 数列 A において、最初に 3 以下となる箇所を探す (2)
- 3 % 2 = 1 となる
- 数列 A において、最初に 1 以下となる箇所を探す (なし)
- よって答えは 1
というように考えることができる。つまり以下のことを繰り返せば OK。
- 数列 において、最初に 以下となる箇所 を二分探索によって探す
- を % で置き換える
これによって毎回のステップで の値はかならず半分以下になるので高々 回のステップで処理が終わる!
まとめると計算量は となる。
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<long long> a({1LL<<60}), b(M); for (int i = 0; i < N; ++i) { long long v; cin >> v; if (a.back() > v) a.push_back(v); } for (int i = 0; i < M; ++i) cin >> b[i]; reverse(a.begin(), a.end()); for (int i = 0; i < M; ++i) { if (i) cout << " "; long long res = b[i]; int it = (int)a.size() - 1; while (it > 0) { it = upper_bound(a.begin(), a.end(), res) - a.begin(); if (it == 0) break; --it; res %= a[it]; } cout << res; } cout << endl; }