fork download
copy 
  1. // TEMPLATE - START
  2. // ----------------------------------------------------
  3. using namespace std;
  4. // ----------------------------------------------------
  5. // DEFINES - START
  6. #include <bits/stdc++.h>
  7. #define FAST                      \
  8.     ios_base::sync_with_stdio(0); \
  9.     cin.tie(0);                   \
  10.     cout.tie(0);
  11. // Strings
  12. #define nl "\n"
  13. #define bl cout << "\n"
  14. #define YES cout << "YES\n"
  15. #define NO cout << "NO\n"
  16. #define yn(x) \
  17.     if (x)    \
  18.         YES;  \
  19.     else      \
  20.         NO;
  21. #define yns(x, s1, s2)      \
  22.     if (x)                  \
  23.         cout << s1 << "\n"; \
  24.     else                    \
  25.         cout << s2 << "\n";
  26. #define fail(cond) \
  27.     if (cond)      \
  28.         return void(NO);
  29. #define success(cond) \
  30.     if (cond)         \
  31.         return void(YES);
  32. #define failS(cond, s) \
  33.     if (cond)          \
  34.         return void(cout << s << nl);
  35. #define successS(cond, s) \
  36.     if (cond)             \
  37.         return void(cout << s << nl);
  38. // Types
  39. #define ll int
  40. #define ld long double
  41. #define ull unsigned long long
  42. #define vl vector<ll>
  43. #define pll pair<ll, ll>
  44. #define vpll vector<pair<ll, ll>>
  45. #define all(x) (x).begin(), (x).end()
  46. #define rall(x) (x).rbegin(), (x).rend()
  47. // Loops
  48. #define lp(i, a, b) for (int i = (a); i < (b); i++)
  49. #define rlp(i, a, b) for (int i = (b) - 1; i >= (a); i--)
  50. #define readlp(arr, a, b) \
  51.     lp(ind, a, b) cin >> arr[ind];
  52. #define writelp(arr, a, b)                     \
  53.     {                                          \
  54.         lp(ind, a, b) cout << arr[ind] << " "; \
  55.         bl;                                    \
  56.     }
  57. #define write(v)              \
  58.     {                         \
  59.         for (auto x : v)      \
  60.             cout << x << " "; \
  61.         bl;                   \
  62.     }
  63. #define vv    \
  64.     ll n;     \
  65.     cin >> n; \
  66.     vl v(n);  \
  67.     readlp(v, 0, v.size());
  68. // DEFINES - END
  69. // ----------------------------------------------------
  70. // DATA_STRUCTURES - START
  71. #include <ext/pb_ds/assoc_container.hpp>
  72. #include <ext/pb_ds/tree_policy.hpp>
  73.  
  74. using namespace __gnu_pbds;
  75.  
  76. // Ordered set (no duplicates, ordered by Key)
  77. template <class Key>
  78. using ordered_set = tree<Key, null_type, less<Key>, rb_tree_tag, tree_order_statistics_node_update>;
  79.  
  80. // Ordered multi-set (allows duplicates, ordered by Key)
  81. template <class Key>
  82. using ordered_multi_set = tree<Key, null_type, less_equal<Key>, rb_tree_tag, tree_order_statistics_node_update>;
  83.  
  84. // Ordered map (Key -> Value, ordered by Key)
  85. template <class Key, class Val>
  86. using ordered_map = tree<Key, Val, less<Key>, rb_tree_tag, tree_order_statistics_node_update>;
  87. // DATA_STRUCTURES - END
  88. // ----------------------------------------------------
  89. // ALGORITHMS - START
  90. // Binary Search Custom:
  91. // To Find...,Logical Condition,If Condition is Met...,Return Value
  92. // Lower Bound (First element ≥x),arr[m] >= x,r = m,r
  93. // Upper Bound (First element >x),arr[m] > x,r = m,r
  94. // Last element <x,arr[m] < x,l = m,l
  95. // Last element ≤x,arr[m] <= x,l = m,l
  96.  
  97. ll lowerBound(vector<ll> &v, ll x)
  98. {
  99.     ll l = -1, r = v.size();
  100.     while (r > l + 1)
  101.     {
  102.         ll m = l + (r - l) / 2;
  103.         if (v[m] >= x)
  104.             r = m;
  105.         else
  106.             l = m;
  107.     }
  108.     return r;
  109. }
  110. // ALGORITHMS - END
  111. // ----------------------------------------------------
  112. // TEMPLATE END
  113.  
  114. // ====================================================
  115.  
  116. // Boody's Code
  117. // 2026-10-07, 19:48:34
  118. // Codeforces - Codeforces Round 1125 (Div. 3)
  119. // F. Tea Blend
  120. // https://c...content-available-to-author-only...s.com/contest/2275/problem/F
  121. // Time limit: 00, Memory limit: 5
  122. // status:
  123. // Time taken:
  124.  
  125. // ----------------------------------------------------
  126.  
  127. set<ll> primeFactors(ll x)
  128. {
  129.     map<ll, ll> factors;
  130.     set<ll> rem;
  131.     while (x % 2 == 0)
  132.         factors[2]++, x = x / 2;
  133.     for (ll i = 3; i * i <= x; i = i + 2)
  134.         while (x % i == 0)
  135.             factors[i]++, x = x / i;
  136.     if (x > 2)
  137.         factors[x]++;
  138.  
  139.     rem.insert(0);
  140.     for (auto [key, val] : factors)
  141.         if (val & 1)
  142.             rem.insert(key);
  143.  
  144.     return rem;
  145. }
  146.  
  147. void solve()
  148. {
  149.     vv;
  150.     map<set<ll>, ll> frq;
  151.     lp(i, 0, n) frq[primeFactors(v[i])]++;
  152.  
  153.     set<ll> curr;
  154.     curr.insert(0);
  155.     ll count = 0;
  156.     lp(i, 0, n)
  157.     {
  158.         for (auto x : primeFactors(v[i]))
  159.         {
  160.             if (curr.find(x) != curr.end() && (x != 0))
  161.                 curr.erase(x);
  162.             else
  163.                 curr.insert(x);
  164.         }
  165.         count += frq[curr];
  166.         if (frq[curr] == 0)
  167.             frq.erase(curr);
  168.     }
  169.     cout << count << nl;
  170. }
  171.  
  172. int main()
  173. {
  174. #ifndef ONLINE_JUDGE
  175.     // freopen("/home/rodex/rubuntu/CS/CP/input.txt", "r", stdin);
  176.     // freopen("/home/rodex/rubuntu/CS/CP/output.txt", "w", stdout);
  177. #endif
  178.     FAST;
  179.     // precomputePrimeFactors();
  180.     int t = 1;
  181.     cin >> t;
  182.     while (t--)
  183.         solve();
  184. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HhCzmT
language:
C++ (gcc 8.3)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!