これ好き!楽しい!!
問題概要
長さ の数列
で定義される、全
ステップの操作が与えられる。操作は整数
に対して行うものであり、
回目の操作は次のものである:
を
%
で置き換える
個の整数
それぞれに対して
ステップの操作を行って得られる結果を答えよ。
制約
考えたこと
愚直にやると となって間に合わない。工夫が必要になる。ここで注目したいことは、たとえば
で割ったあとに、
で割っても値は変わらない。一般に、
であるとき、
%
は最初から
未満なので、%
をしても値は変化しない
ということになる。よって、数列 において、
(
) となっている部分はあらかじめ削除することができる。よって数列
は単調減少であるものと考えてよい!!
そうとわかれば二分探索
そうとわかれば、数列 による操作を効率化できる。具体的には、たとえば
に対して
を適用するとき
- まず 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; }