fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <unordered_map>
  5. #include <iomanip>
  6. #include <cmath>
  7. #include <set>
  8. using namespace std;
  9.  
  10. int gcd(int a, int b) {
  11.     return b == 0 ? a : gcd(b, a % b);
  12. }
  13. long long int mod = 998244353;
  14.  
  15. long long int poww(long long int a, int x) {
  16.     if (x == 1) {
  17.         return a;
  18.     } else if (x == 0) {
  19.         return 1;
  20.     }
  21.  
  22.     long long int temp = poww(a, x / 2);
  23.     long long int val = (temp * temp) % mod;
  24.  
  25.     if (x % 2) {
  26.         return (val * a) % mod;
  27.     } 
  28.     return val;
  29. }
  30.  
  31.  
  32. int main() {
  33.     int test_cases = 1;
  34.     cin >> test_cases;
  35.  
  36.     // vector<vector<int> > mp(5010, vector<int>(5010, 0));
  37.  
  38.     // for (int i = 0; i < 5010; i++) {
  39.     //     for (int j = 0; j < 5010; j++) {
  40.     //         mp[i][j] = gcd(i, j);
  41.     //     }
  42.     // }
  43.  
  44.     while(test_cases--) {
  45.  
  46.         int n;
  47.         cin >> n;
  48.  
  49.         vector<int> a(n);
  50.  
  51.         for (int i = 0; i < n; i++) {
  52.             cin >> a[i];
  53.         }
  54.         int x = 1, flag = 0;;
  55.         for (int i = 0; i < n - 1; i++) {
  56.             if (a[i + 1] % (a[i])) {
  57.                 a[i] /= x;
  58.                 if (a[i + 1] % (a[i])) {
  59.                     int lc = gcd(a[i], a[i + 1]);
  60.                     x *= a[i] / lc;
  61.                 }
  62.             }
  63.             cout << x << " " <<i << endl;
  64.         }
  65.  
  66.         cout << x << endl;
  67.  
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
4
2
2 4
3
1 1000000000 500000000
4
4 8 4 8
7
42 42 14 84 28 73080 255780
stdout
copy 
1 0
1
1 0
2 1
2
1 0
2 1
2 2
2
1 0
3 1
3 2
3 3
3 4
6 5
6
https://ideone.com/4mlTJM
language:
C++ (gcc 8.3)
created:
2 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!