fork download
copy 
  1. /*
  2. PROBLEM: Maximize Pairs with Different Square-Free Kernels
  3.  
  4. Given:
  5. - N numbers in an array
  6. - K operations allowed
  7. - Each operation changes a number to have a new unique kernel
  8.  
  9. Square-Free Kernel Definition:
  10. - For a number, factor it into primes
  11. - Multiply only the primes that appear an ODD number of times
  12. - Example: 72 = 2^3 * 3^2 → kernel = 2 (only 2 appears odd times)
  13. - Example: 50 = 2 * 5^2 → kernel = 2 (only 2 appears odd times)
  14. - Example: 18 = 2 * 3^2 → kernel = 2
  15.  
  16. Goal: Two numbers form a "good pair" if their kernels are DIFFERENT.
  17. Maximize the number of good pairs.
  18.  
  19. Key Insight:
  20. - If all N numbers have different kernels → we can make N/2 pairs (all good)
  21. - If many numbers share the same kernel → they can't pair with each other
  22. - We can use K operations to move numbers to new unique kernels
  23. - Strategy: Reduce the maximum frequency of any kernel
  24.  
  25. Approach:
  26. 1. Calculate kernel for each number
  27. 2. Count how many numbers have each kernel
  28. 3. Binary search: what's the minimum max-frequency we can achieve with K ops?
  29. 4. Answer = min(N/2, N - final_max_freq)
  30.    - N/2 is the max possible pairs
  31.    - N - max_freq is how many can pair with different kernels
  32.  
  33. Time: O(N√M + log(max_freq) * unique_kernels) where M is max element
  34. */
  35.  
  36. #include <bits/stdc++.h>
  37. using namespace std;
  38.  
  39. // Find all primes up to limit
  40. vector<int> sieve(int lim) {
  41.     vector<bool> ok(lim + 1, true);
  42.     ok[0] = ok[1] = false;
  43.  
  44.     for (int i = 2; i * i <= lim; i++) {
  45.         if (ok[i]) {
  46.             for (int j = i * i; j <= lim; j += i) {
  47.                 ok[j] = false;
  48.             }
  49.         }
  50.     }
  51.  
  52.     vector<int> p;
  53.     for (int i = 2; i <= lim; i++) {
  54.         if (ok[i]) p.push_back(i);
  55.     }
  56.     return p;
  57. }
  58.  
  59. // Get square-free kernel: multiply primes with odd exponent
  60. long long calc(long long x, const vector<int>& p) {
  61.     long long res = 1;
  62.  
  63.     for (int pr : p) {
  64.         if ((long long)pr * pr > x) break;
  65.  
  66.         int cnt = 0;
  67.         while (x % pr == 0) {
  68.             x /= pr;
  69.             cnt++;
  70.         }
  71.  
  72.         // If odd exponent, include this prime
  73.         if (cnt & 1) res *= pr;
  74.     }
  75.  
  76.     // If x > 1 now, it's a prime with exponent 1
  77.     if (x > 1) res *= x;
  78.  
  79.     return res;
  80. }
  81.  
  82. int main() {
  83.     ios::sync_with_stdio(false);
  84.     cin.tie(nullptr);
  85.  
  86.     int n;
  87.     long long k;
  88.     cin >> n >> k;
  89.  
  90.     vector<long long> a(n);
  91.     long long mx = 0;
  92.  
  93.     for (int i = 0; i < n; i++) {
  94.         cin >> a[i];
  95.         mx = max(mx, a[i]);
  96.     }
  97.  
  98.     if (n < 2) {
  99.         cout << 0 << "\n";
  100.         return 0;
  101.     }
  102.  
  103.     // Get primes up to sqrt(max)
  104.     int sq = (int)sqrt(mx);
  105.     vector<int> p = sieve(max(1, sq));
  106.  
  107.     // Count kernel frequencies
  108.     map<long long, int> cnt;
  109.     for (long long x : a) {
  110.         long long ker = calc(x, p);
  111.         cnt[ker]++;
  112.     }
  113.  
  114.     // Extract frequencies
  115.     vector<int> f;
  116.     int mf = 0;
  117.     for (auto [ker, c] : cnt) {
  118.         f.push_back(c);
  119.         mf = max(mf, c);
  120.     }
  121.  
  122.     // Binary search: minimum achievable max frequency
  123.     int lo = 1, hi = mf;
  124.  
  125.     // Check if we can reduce all frequencies to at most t
  126.     auto check = [&](int t) -> bool {
  127.         long long ops = 0;
  128.         for (int c : f) {
  129.             if (c > t) {
  130.                 ops += (c - t);
  131.                 if (ops > k) return false;
  132.             }
  133.         }
  134.         return true;
  135.     };
  136.  
  137.     while (lo < hi) {
  138.         int mid = lo + (hi - lo) / 2;
  139.         if (check(mid)) {
  140.             hi = mid;
  141.         } else {
  142.             lo = mid + 1;
  143.         }
  144.     }
  145.  
  146.     int best = lo;
  147.  
  148.     // Maximum pairs we can form
  149.     long long total = n / 2;
  150.  
  151.     // Answer: min of total pairs or (n - max_freq)
  152.     long long ans = min(total, (long long)(n - best));
  153.  
  154.     cout << ans << "\n";
  155.  
  156.     return 0;
  157. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2631
https://ideone.com/JPHCvQ
language:
C++14 (gcc 8.3)
created:
1 day 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!