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. // Sieve of Eratosthenes: find all prime numbers up to limit
  40. vector<int> sieve(int lim) {
  41.     vector<bool> ok(lim + 1, true);
  42.     ok[0] = ok[1] = false;  // 0 and 1 are not prime
  43.  
  44.     // Mark multiples of each prime as not prime
  45.     for (int i = 2; i * i <= lim; i++) {
  46.         if (ok[i]) {
  47.             // Mark all multiples of i starting from i*i
  48.             for (int j = i * i; j <= lim; j += i) {
  49.                 ok[j] = false;
  50.             }
  51.         }
  52.     }
  53.  
  54.     // Collect all primes
  55.     vector<int> p;
  56.     for (int i = 2; i <= lim; i++) {
  57.         if (ok[i]) p.push_back(i);
  58.     }
  59.     return p;
  60. }
  61.  
  62. // Calculate square-free kernel of x
  63. // Kernel = product of all prime factors with ODD exponent
  64. long long calc(long long x, const vector<int>& p) {
  65.     long long res = 1;
  66.  
  67.     // Check each prime up to sqrt(x)
  68.     for (int pr : p) {
  69.         if ((long long)pr * pr > x) break;
  70.  
  71.         // Count how many times pr divides x
  72.         int cnt = 0;
  73.         while (x % pr == 0) {
  74.             x /= pr;
  75.             cnt++;
  76.         }
  77.  
  78.         // If exponent is odd, include this prime in kernel
  79.         if (cnt & 1) res *= pr;
  80.     }
  81.  
  82.     // If x > 1 remains, it's a prime factor with exponent 1 (odd)
  83.     if (x > 1) res *= x;
  84.  
  85.     return res;
  86. }
  87.  
  88. int main() {
  89.     ios::sync_with_stdio(false);
  90.     cin.tie(nullptr);
  91.  
  92.     int n;
  93.     long long k;
  94.     cin >> n >> k;
  95.  
  96.     vector<long long> a(n);
  97.     long long mx = 0;
  98.  
  99.     for (int i = 0; i < n; i++) {
  100.         cin >> a[i];
  101.         mx = max(mx, a[i]);  // Track maximum value
  102.     }
  103.  
  104.     // Edge case: can't form pairs with less than 2 elements
  105.     if (n < 2) {
  106.         cout << 0 << "\n";
  107.         return 0;
  108.     }
  109.  
  110.     // Generate all primes up to sqrt(max_value)
  111.     // We only need primes up to sqrt because larger primes appear with exponent 1
  112.     int sq = (int)sqrt(mx);
  113.     vector<int> p = sieve(max(1, sq));
  114.  
  115.     // Calculate kernel for each number and count frequencies
  116.     map<long long, int> cnt;
  117.     for (long long x : a) {
  118.         long long ker = calc(x, p);
  119.         cnt[ker]++;
  120.     }
  121.  
  122.     // Extract all frequency values
  123.     vector<int> f;
  124.     int mf = 0;  // Maximum frequency
  125.     for (auto [ker, c] : cnt) {
  126.         f.push_back(c);
  127.         mf = max(mf, c);
  128.     }
  129.  
  130.     // Binary search to find minimum achievable max frequency with k operations
  131.     int lo = 1, hi = mf;
  132.  
  133.     // Check if we can reduce all frequencies to at most t using k operations
  134.     auto check = [&](int t) -> bool {
  135.         long long ops = 0;  // Operations needed
  136.         for (int c : f) {
  137.             // If frequency c > t, we need to move (c - t) elements
  138.             if (c > t) {
  139.                 ops += (c - t);
  140.                 if (ops > k) return false;  // Too many operations needed
  141.             }
  142.         }
  143.         return true;  // Can achieve with <= k operations
  144.     };
  145.  
  146.     // Binary search: find smallest t such that check(t) is true
  147.     while (lo < hi) {
  148.         int mid = lo + (hi - lo) / 2;
  149.         if (check(mid)) {
  150.             hi = mid;  // Can achieve mid, try smaller
  151.         } else {
  152.             lo = mid + 1;  // Can't achieve mid, need larger
  153.         }
  154.     }
  155.  
  156.     int best = lo;  // Best max frequency we can achieve
  157.  
  158.     // Maximum pairs possible = n/2 (each pair uses 2 elements)
  159.     long long total = n / 2;
  160.  
  161.     // Elements that can pair with different kernels = n - best
  162.     // (If max freq is 'best', at most 'best' elements share same kernel)
  163.     // Answer is minimum of: total possible pairs, or elements with different kernels
  164.     long long ans = min(total, (long long)(n - best));
  165.  
  166.     cout << ans << "\n";
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2709
https://ideone.com/Cokfa4
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!