Dang_Quan_10_Tin

APPLES

Sep 20th, 2021 (edited)
380
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. template <class T>
  9. void read(T &x)
  10. {
  11.     x = 0;
  12.     register int c;
  13.     while ((c = getchar()) && (c > '9' || c < '0'))
  14.         ;
  15.     for (; c >= '0' && c <= '9'; c = getchar())
  16.         x = x * 10 + c - '0';
  17. }
  18.  
  19. constexpr bool typetest = 1;
  20. constexpr int N = 2e4 + 5;
  21. int n;
  22. ll v, a[N];
  23.  
  24. /*
  25. Gọi v_i là số táo người thứ i còn sau khi chia kết thúc
  26.     sum là tổng số táo của n người
  27.  
  28. * v_i = [          a[i] * 2^(i - 1)           -   (sum - a[i] * 2^(i - 1)) ] * 2^(n - i)
  29.           trước khi người i chia táo       sau khi chia táo       được chia tiếp theo
  30.  
  31.       = a_i * 2^n - sum * 2 ^ (n - i)
  32.  
  33. mà v_i = v_(i + 1)
  34. => [ a_i - a_(i + 1) ] = sum / 2^(i + 1)
  35.  
  36. => a_i = a_1 - sum * (1 / 4 + 1 / 8 + ... + 1 / 2^i) = a_1 - sum * (1/2 -  1/2^i) (1)
  37.  
  38. Thế (1) vào công thức sum = a_1 + a_2 + ... + a_n ta có
  39. sum = n * a_1 * 2^n / [2^n + (n - 2) * 2^(n - 1) + 1]
  40.  
  41. Từ đó tính được dãy a
  42. */
  43.  
  44. void Read()
  45. {
  46.     cin >> n >> v;
  47. }
  48.  
  49. ll Get(ll x, ll y)
  50. {
  51.     a[n] = x;
  52.     a[n - 1] = y;
  53.  
  54.     for (int i = n - 2; i; --i)
  55.         a[i] = (3 * a[i + 1] - 2 * a[i + 2]);
  56.  
  57.     return a[1];
  58. }
  59.  
  60. void Solve()
  61. {
  62.     if (n == 1)
  63.     {
  64.         cout << v << "\n";
  65.         return;
  66.     } /*
  67.     if (n == 2)
  68.     {
  69.         if (v % 5 != 0)
  70.             cout << "-1\n";
  71.         else
  72.             cout << v << " " << v * 3 / 5 << "\n";
  73.         return;
  74.     }
  75.  
  76.     if (n == 3)
  77.     {
  78.         ll a1 = 10, b1 = 2, c1 = 6 * v,
  79.            a2 = 7, b2 = -9, c2 = v;
  80.  
  81.         ll d = a1 * b2 - a2 * b1,
  82.            dx = c1 * b2 - c2 * b1,
  83.            dy = a1 * c2 - a2 * c1;
  84.  
  85.         if (dx % d != 0 || dy % d != 0)
  86.         {
  87.             cout << "-1\n";
  88.             return;
  89.         }
  90.         dx /= d;
  91.         dy /= d;
  92.  
  93.         if (dx < 0 || dy < 0)
  94.         {
  95.             cout << "-1\n";
  96.             return;
  97.         }
  98.  
  99.         cout << v << " " << dx << " " << dy << '\n';
  100.  
  101.         return;
  102.     }*/
  103.  
  104.     ll x = n * v,
  105.        y = (1ll << n) + (n - 2) * (1ll << (n - 1)) + 1,
  106.        z = 1ll << n;
  107.  
  108.     ll u = __gcd(x, y);
  109.     x /= u;
  110.     y /= u;
  111.     u = __gcd(z, y);
  112.     z /= u;
  113.     y /= u;
  114.  
  115.     if (y != 1)
  116.     {
  117.         cout << "-1\n";
  118.         return;
  119.     }
  120.  
  121.     x *= z;
  122.     //cout << x << " " << y << " " << z << "\n";
  123.  
  124.     if (x % 4 != 0)
  125.     {
  126.         cout << "-1\n";
  127.         return;
  128.     }
  129.     x /= 4;
  130.  
  131.     a[1] = v;
  132.  
  133.     for (int i = 2; i <= n; ++i)
  134.     {
  135.         a[i] = a[i - 1] - x;
  136.         if (i != n && (x & 1))
  137.         {
  138.             cout << "-1\n";
  139.             return;
  140.         }
  141.         x /= 2;
  142.     }
  143.  
  144.     for (int i = 1; i <= n; ++i)
  145.         cout << a[i] << " ";
  146.     cout << "\n";
  147. }
  148.  
  149. int32_t main()
  150. {
  151.     ios::sync_with_stdio(0);
  152.     cin.tie(0);
  153.     cout.tie(0);
  154.     int t(1);
  155.     if (typetest)
  156.         cin >> t;
  157.     for (int _ = 1; _ <= t; ++_)
  158.     {
  159.         //cout << "Case #" << _ << ": ";
  160.         Read();
  161.         Solve();
  162.     }
  163.     //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  164. }
Advertisement
Add Comment
Please, Sign In to add comment