fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Helper function to compute the Greatest Common Divisor
  9. long long gcd(long long a, long long b) {
  10.     while (b) {
  11.         a %= b;
  12.         swap(a, b);
  13.     }
  14.     return a;
  15. }
  16.  
  17. int main() {
  18.     // Optimize standard I/O operations for performance
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(NULL);
  21.  
  22.     int n;
  23.     if (!(cin >> n)) return 0;
  24.  
  25.     vector<long long> a(n + 1), b(n + 1);
  26.     long long g = 0;
  27.     for (int i = 1; i <= n; ++i) {
  28.         cin >> a[i];
  29.         g = gcd(g, a[i]);
  30.     }
  31.     for (int i = 1; i <= n; ++i) {
  32.         cin >> b[i];
  33.     }
  34.  
  35.     // If the overall GCD is already 1, no operations are required.
  36.     if (g == 1) {
  37.         cout << 0 << "\n";
  38.         return 0;
  39.     }
  40.  
  41.     // Extract unique prime factors of the initial overall GCD
  42.     vector<long long> primes;
  43.     long long temp = g;
  44.     for (long long i = 2; i * i <= temp; ++i) {
  45.         if (temp % i == 0) {
  46.             primes.push_back(i);
  47.             while (temp % i == 0) {
  48.                 temp /= i;
  49.             }
  50.         }
  51.     }
  52.     if (temp > 1) {
  53.         primes.push_back(temp);
  54.     }
  55.  
  56.     int k = primes.size();
  57.     int max_mask = 1 << k;
  58.  
  59.     // dp[mask] stores the minimum cost to achieve the state represented by mask
  60.     // -1 denotes an unreachable state
  61.     vector<long long> dp(max_mask, -1);
  62.     dp[0] = 0;
  63.  
  64.     for (int i = 1; i <= n; ++i) {
  65.         int mask_i = 0;
  66.         for (int j = 0; j < k; ++j) {
  67.             if (b[i] % primes[j] != 0) {
  68.                 mask_i |= (1 << j);
  69.             }
  70.         }
  71.  
  72.         // If this element eliminates no prime factors, skip it
  73.         if (mask_i == 0) continue;
  74.  
  75.         long long cost = 1LL * i * i + i;
  76.  
  77.         // Update the DP table from top to bottom to use only one array copy
  78.         for (int mask = max_mask - 1; mask >= 0; --mask) {
  79.             if (dp[mask] != -1) {
  80.                 int next_mask = mask | mask_i;
  81.                 if (dp[next_mask] == -1 || dp[mask] + cost < dp[next_mask]) {
  82.                     dp[next_mask] = dp[mask] + cost;
  83.                 }
  84.             }
  85.         }
  86.     }
  87.  
  88.     // Output the minimum cost to eliminate all prime factors, or -1 if impossible
  89.     cout << dp[max_mask - 1] << "\n";
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4ujnZ8
language:
C++ (gcc 8.3)
created:
17 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!