Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- template <class T>
- void read(T &x)
- {
- x = 0;
- register int c;
- while ((c = getchar()) && (c > '9' || c < '0'))
- ;
- for (; c >= '0' && c <= '9'; c = getchar())
- x = x * 10 + c - '0';
- }
- constexpr bool typetest = 1;
- constexpr int N = 2e4 + 5;
- int n;
- ll v, a[N];
- /*
- Gọi v_i là số táo người thứ i còn sau khi chia kết thúc
- sum là tổng số táo của n người
- * v_i = [ a[i] * 2^(i - 1) - (sum - a[i] * 2^(i - 1)) ] * 2^(n - i)
- trước khi người i chia táo sau khi chia táo được chia tiếp theo
- = a_i * 2^n - sum * 2 ^ (n - i)
- mà v_i = v_(i + 1)
- => [ a_i - a_(i + 1) ] = sum / 2^(i + 1)
- => a_i = a_1 - sum * (1 / 4 + 1 / 8 + ... + 1 / 2^i) = a_1 - sum * (1/2 - 1/2^i) (1)
- Thế (1) vào công thức sum = a_1 + a_2 + ... + a_n ta có
- sum = n * a_1 * 2^n / [2^n + (n - 2) * 2^(n - 1) + 1]
- Từ đó tính được dãy a
- */
- void Read()
- {
- cin >> n >> v;
- }
- ll Get(ll x, ll y)
- {
- a[n] = x;
- a[n - 1] = y;
- for (int i = n - 2; i; --i)
- a[i] = (3 * a[i + 1] - 2 * a[i + 2]);
- return a[1];
- }
- void Solve()
- {
- if (n == 1)
- {
- cout << v << "\n";
- return;
- } /*
- if (n == 2)
- {
- if (v % 5 != 0)
- cout << "-1\n";
- else
- cout << v << " " << v * 3 / 5 << "\n";
- return;
- }
- if (n == 3)
- {
- ll a1 = 10, b1 = 2, c1 = 6 * v,
- a2 = 7, b2 = -9, c2 = v;
- ll d = a1 * b2 - a2 * b1,
- dx = c1 * b2 - c2 * b1,
- dy = a1 * c2 - a2 * c1;
- if (dx % d != 0 || dy % d != 0)
- {
- cout << "-1\n";
- return;
- }
- dx /= d;
- dy /= d;
- if (dx < 0 || dy < 0)
- {
- cout << "-1\n";
- return;
- }
- cout << v << " " << dx << " " << dy << '\n';
- return;
- }*/
- ll x = n * v,
- y = (1ll << n) + (n - 2) * (1ll << (n - 1)) + 1,
- z = 1ll << n;
- ll u = __gcd(x, y);
- x /= u;
- y /= u;
- u = __gcd(z, y);
- z /= u;
- y /= u;
- if (y != 1)
- {
- cout << "-1\n";
- return;
- }
- x *= z;
- //cout << x << " " << y << " " << z << "\n";
- if (x % 4 != 0)
- {
- cout << "-1\n";
- return;
- }
- x /= 4;
- a[1] = v;
- for (int i = 2; i <= n; ++i)
- {
- a[i] = a[i - 1] - x;
- if (i != n && (x & 1))
- {
- cout << "-1\n";
- return;
- }
- x /= 2;
- }
- for (int i = 1; i <= n; ++i)
- cout << a[i] << " ";
- cout << "\n";
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t(1);
- if (typetest)
- cin >> t;
- for (int _ = 1; _ <= t; ++_)
- {
- //cout << "Case #" << _ << ": ";
- Read();
- Solve();
- }
- //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment