結果
問題 | No.1243 約数加算 |
ユーザー |
|
提出日時 | 2020-10-02 23:16:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 3,144 bytes |
コンパイル時間 | 1,968 ms |
コンパイル使用メモリ | 197,064 KB |
最終ジャッジ日時 | 2025-01-15 01:17:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
#pragma region template#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using ld = long double;using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vld = vector<ld>;using vvld = vector<vld>;using vvvld = vector<vvld>;using vs = vector<string>;using pll = pair<ll, ll>;using vp = vector<pll>;template <typename T>using pqrev = priority_queue<T, vector<T>, greater<T>>;#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)#define ALL(a) (a).begin(), (a).end()#define SZ(x) ((ll)(x).size())//*constexpr ll MOD = 1e9 + 7;/*/constexpr ll MOD = 998244353;//*/constexpr ll INF = 1e+18;constexpr ld EPS = 1e-12L;constexpr ld PI = 3.14159265358979323846L;constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }template <typename S, typename T>constexpr bool chmax(S &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <typename S, typename T>constexpr bool chmin(S &a, const T &b) {if (b < a) {a = b;return 1;}return 0;}#ifdef OJ_LOCAL#include "dump.hpp"#else#define dump(...) ((void)0)#endiftemplate <typename T>bool print_(const T &a) {cout << a;return true;}template <typename T>bool print_(const vector<T> &vec) {for (auto &a : vec) {cout << a;if (&a != &vec.back()) {cout << " ";}}return false;}template <typename T>bool print_(const vector<vector<T>> &vv) {for (auto &v : vv) {for (auto &a : v) {cout << a;if (&a != &v.back()) {cout << " ";}}if (&v != &vv.back()) {cout << "\n";}}return false;}void print() { cout << "\n"; }template <typename Head, typename... Tail>void print(Head &&head, Tail &&... tail) {bool f = print_(head);if (sizeof...(tail) != 0) {cout << (f ? " " : "\n");}print(forward<Tail>(tail)...);}#pragma endregionvoid Pr(bool f){cout << (f ? "Yes" : "No") << "\n";exit(0);}ll msb(ll x){ll i = 1;while(i <= x) i <<= 1;return i >> 1;}ll leastbit(ll x){assert(x > 0);ll i = 1;while(!(i & x)) i <<= 1;return i;}vll ans;void solve(ll a, ll b){while(1){if((a&b) == b && msb(a-b)<leastbit(b)) break;ans.emplace_back(leastbit(b));b += leastbit(b);}repb(i, 62){ll j = 1ll << i;if((j & a) && (!(j & b))){ans.emplace_back(j);b += j;}}}int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(20);ll T;cin >> T;while(T--){ans.clear();ll a, b;cin >> a >> b;solve(b, a);print(SZ(ans));print(ans);assert(a + accumulate(ALL(ans), 0ll) == b);rep(i, SZ(ans)){assert(a%ans[i]==0);a += ans[i];}}}