fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 1e6 + 5;
  7. int n;
  8. void solve() {
  9.     cin >> n;
  10.     vector<int> a;
  11.     for (int i = 1; i <= n; i++) {
  12.         int x;
  13.         cin >> x;
  14.         a.push_back(x);
  15.     }
  16.     int ans = 0;
  17.     for (int i = 0; i < a.size();) {
  18.         if (i + 1 < (int)a.size()) {
  19.             if (__gcd(a[i], a[i + 1]) == 1 || max(a[i], a[i + 1]) % min(a[i], a[i + 1]) == 0) {
  20.                 i += 2;
  21.             }
  22.             else {
  23.                 a.push_back(1);
  24.                 a[i] = 1;
  25.             }
  26.         }
  27.         else {
  28.             a.push_back(1);
  29.         }
  30.         ans++;
  31.     }
  32.     cout << ans << "\n";
  33. }
  34. signed main() {
  35.     cin.tie(NULL)->sync_with_stdio(false);
  36.     if(ifstream("Input.inp")) {
  37.         freopen("Input.inp", "r", stdin);
  38.         freopen("Output.out", "w", stdout);
  39.     }
  40.     int tt; cin >> tt;
  41.     while(tt--) {
  42.         solve();
  43.     }
  44.     return 0;
  45. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VSuSOG
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!