fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define SPED ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  6. #define endl "\n"
  7.  
  8. const int MAXA = 10000001;
  9. int n;
  10. int a[1000005];
  11. int min_idx1[MAXA], min_idx2[MAXA]; 
  12.  
  13. void better(int val_idx, int g) {
  14.     if (min_idx1[g] == 0) {
  15.         min_idx1[g] = val_idx;
  16.     } else if (a[val_idx] < a[min_idx1[g]]) {
  17.         min_idx2[g] = min_idx1[g];
  18.         min_idx1[g] = val_idx;
  19.     } else if (min_idx2[g] == 0 || a[val_idx] < a[min_idx2[g]]) {
  20.         min_idx2[g] = val_idx;
  21.     }
  22. }
  23.  
  24. int main() {
  25.     SPED;
  26.     if (fopen("llcm.inp", "r")) {
  27.         freopen("llcm.inp", "r", stdin);
  28.         freopen("llcm.out", "w", stdout);
  29.     }
  30.  
  31.     cin >> n;
  32.     int mx = 0;
  33.     for (int i = 1; i <= n; i++) {
  34.         cin >> a[i];
  35.         if (a[i] > mx) mx = a[i];
  36.     }
  37.     for (int i = 1; i <= n; i++) {
  38.         better(i, a[i]);
  39.     }
  40.  
  41.     for (int g = 1; g <= mx; g++) {
  42.         for (int hmm = 2 * g; hmm <= mx; hmm += g) {
  43.             if (min_idx1[hmm] == 0) continue;
  44.  
  45.             better(min_idx1[hmm], g);
  46.             if (min_idx2[hmm] != 0) {
  47.                 better(min_idx2[hmm], g);
  48.             }
  49.         }
  50.     }
  51.  
  52.     long long mini = 2e18;
  53.     int res1 = -1, res2 = -1;
  54.  
  55.     for (int g = 1; g <= mx; g++) {
  56.         if (min_idx1[g] != 0 && min_idx2[g] != 0) {
  57.             long long v1 = a[min_idx1[g]];
  58.             long long v2 = a[min_idx2[g]];
  59.             long long res = (v1 * v2) / g;
  60.             if (res < mini) {
  61.                 mini = res;
  62.                 res1 = min_idx1[g];
  63.                 res2 = min_idx2[g];
  64.             }
  65.         }
  66.     }
  67.  
  68.     if (res1 > res2) swap(res1, res2);
  69.     cout << res1 << " " << res2 << endl;
  70.  
  71.     return 0;
  72. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
-1 -1
https://ideone.com/uZhBwT
language:
C++14 (gcc 8.3)
created:
3 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!