fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int MAX_VAL = 1e6;  // Maximum possible value of elements in the array
  6.  
  7. // Function to calculate sum of GCD over all pairs
  8. long long gcd_sum_over_pairs(const vector<int>& arr) {
  9.     // Step 1: Create a frequency array
  10.     vector<int> freq(MAX_VAL + 1, 0);
  11.     for (int num : arr) {
  12.         freq[num]++;
  13.     }
  14.  
  15.     // Step 2: Create an array to store the number of pairs with GCD exactly g
  16.     vector<long long> gcd_pairs(MAX_VAL + 1, 0);
  17.  
  18.     // Step 3: For each gcd value `g`, calculate how many multiples of `g` exist
  19.     for (int g = MAX_VAL; g >= 1; g--) {
  20.         long long count_g = 0;
  21.  
  22.         // Count numbers divisible by g (these include numbers divisible by 2g, 3g, etc.)
  23.         for (int multiple = g; multiple <= MAX_VAL; multiple += g) {
  24.             count_g += freq[multiple];
  25.         }
  26.  
  27.         // If there are at least 2 numbers divisible by g
  28.         if (count_g >= 2) {
  29.             // Total pairs where GCD >= g
  30.             gcd_pairs[g] = count_g * (count_g - 1) / 2;
  31.  
  32.             // Subtract pairs where GCD is a multiple of g (like 2g, 3g, etc.)
  33.             for (int multiple = 2 * g; multiple <= MAX_VAL; multiple += g) {
  34.                 gcd_pairs[g] -= gcd_pairs[multiple];
  35.             }
  36.         }
  37.     }
  38.  
  39.     // Step 4: Calculate the total sum of GCDs over all pairs
  40.     long long result = 0;
  41.     for (int g = 1; g <= MAX_VAL; g++) {
  42.         result += g * gcd_pairs[g];  // Add contribution from all pairs where GCD is exactly g
  43.     }
  44.  
  45.     return result;
  46. }
  47.  
  48. int main() {
  49.     // Example usage
  50.     int n;
  51.     cin >> n;
  52.     int x;
  53.     vector<int> arr;
  54.     for(int i = 0; i < n; ++i){
  55.     	cin >> x;
  56.     	arr.push_back(x);
  57.     }
  58.  
  59.     // Call the function and print the result
  60.     cout << gcd_sum_over_pairs(arr) << endl;
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.03s 15084KB
comments (?)
stdin
copy 
4
3 9 6 10
stdout
copy 
13
https://ideone.com/ivHJVc
language:
C++14 (gcc 8.3)
created:
5 days 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!