[yukicoder] No. 1243 約数加算
問題
方針
\( 2A \leq B \) のとき、\( A \leftarrow 2A \) と可能な限り更新します。このとき、\( A \) は \(2^nA \leq B\) を満たす最大の非負整数 \( n \) を用いて、
\[ A \leftarrow 2^nA \]
と更新したことになります。次に、\( 2^nA + 2^mA \leq B \ (0 \leq m < n)\) を満たす \( m \) を求めて、
\[ A \leftarrow 2^nA + 2^mA\]
と更新します。このような更新を続けると \( A \) は、
\[ A \leftarrow 2^{n_1}A + 2^{n_2}A + \cdots + 2^{n_k}A \ (n_1 > n_2 > \cdots > n_k \geq 0)\]
と更新されることになります。このとき、\( 0 \leq B – A \leq A – 1 \) となります。また、\( B = A \) のとき答え出力します。
次に、\( A \bmod 2 = 1 \) のとき、\( A \leftarrow A + 1 \) と更新します。
ここで、奇数 \( p \) と非負整数 \( l \) を用いて、\( A = 2^lp \) と表すことができます。このとき、\( A \) は \(2^l \) の約数を持ちます。また、奇数 \( q \) を用いて、\( 2^lp + 2^l = 2^{l + 1} q \) と表すことができます。したがって、\( 2^l \) を \( A \) の約数として、\( A + 2^r \leq B \ (0 \leq r \leq l)\) を満たす最大の \( r \) を求めて、\( A \leftarrow A + 2^r \) と更新します。これを \( A = B \) となるまで続けます。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll A, B; vector<ll> v; ll my_pow(ll x, ll n) { if (n == 0) return 1; if (n % 2 == 0) return my_pow(x * x, n / 2); return x * my_pow(x, n - 1); } ll a; int t; void add(int n) { t = -1; for (int i = 1; i <= n; i++) { if (B - a - A * my_pow(2, i) >= 0) { t = i; } } if (t != -1) { v.push_back(A * my_pow(2, t)); a += v.back(); } } void add2() { ll k = a; int g = 0; while (k % 2 == 0 && B - a - my_pow(2, g) >= 0) { k /= 2; g++; } if (g == 0) return; if (B - a - my_pow(2, g) < 0) g--; v.push_back(my_pow(2, g)); a += my_pow(2, g); } void solve() { v.clear(); a = A; for (int i = 0; i < 120; i++) { if (B >= 2 * a) { v.push_back(a); a *= 2; } } a = A; for (ll i : v) { a += i; } t = v.size(); for (int i = 0; i < 70; i++) { if (t == -1) break; add(t); } if (B - a - A >= 0) { v.push_back(A); a += A; } if (a % 2 == 1 && B - a != 0) { a++; v.push_back(1); } for (int i = 0; i < 70; i++) { add2(); } ll n = A; cout << v.size() << "\n"; for (int i = 0; i < v.size(); i++) { if (i == v.size() - 1) { cout << v.back() << "\n"; } else { cout << v[i] << " "; } n += v[i]; } } int main() { int T; cin >> T; for (int i = 0; i < T; i++) { cin >> A >> B; solve(); } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません