Submission #7098942

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define INF 1e9;
using namespace std;
typedef long long ll;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) { cin >> a[i]; }
  sort(a.begin(), a.end());
  ll div;
  ll cnt = 1;
  if (a[0] == 1) {
    div = a[1];
    if (a[1] != 2) {
      cnt++;
    }
  } else {
    div = a[0];
  }
  FOR(i, cnt, n) {
    if (a[i] % div == 0) {
      continue;
    } else {
      cnt++;
      div = (div * a[i]) / __gcd(div, a[i]);
    }
  }

  cout << cnt << endl;
  return 0;
}

Submission Info

Judge Result