結果

問題 No.917 Make One With GCD
コンテスト
ユーザー risujiroh
提出日時 2019-10-25 21:59:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,418 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 183,344 KB
実行使用メモリ 55,828 KB
最終ジャッジ日時 2024-09-13 03:35:06
合計ジャッジ時間 8,278 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<class Z> V<Z> divisor(Z n) {
  V<Z> res;
  Z i;
  for (i = 1; i * i < n; ++i) if (n % i == 0) res.push_back(i), res.push_back(n / i);
  if (i * i == n) res.push_back(i);
  sort(begin(res), end(res));
  return res;
}

V<> sieve(int n) {
  V<bool> b((n + 1) / 3, true);
  V<> res{2, 3};
  for (int p = 5, d = 2; p * p < n; p += d, d = 6 - d) if (b[p / 3]) {
    for (int i = 5 * p, e = 2 * p; i < n; i += e, e = 6 * p - e) b[i / 3] = false;
  }
  for (int p = 5, d = 2; p < n; p += d, d = 6 - d) if(b[p / 3]) res.push_back(p);
  while (!res.empty() and res.back() >= n) res.pop_back();
  return res;
}

constexpr int L = 1e8;

template<class T> void ifmult(map<int, T>& a, const V<>& ps) {
  int n = L + 1;
  for (int p : ps) {
    for (int i = 1; i * p < n; ++i) if (a.count(i * p)) {
      a[i] -= a[i * p];
    }
  }
}


int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  map<int, lint> c;
  for (int _ = 0; _ < n; ++_) {
    int a; cin >> a;
    for (int d : divisor(a)) {
      ++c[d];
    }
  }
  for (auto&& e : c) if (e.second) {
    e.second = (1LL << e.second) - 1;
  }
  // for (const auto& e : c) {
  //   cerr << e.first << ' ' << e.second << '\n';
  // }
  ifmult(c, sieve(L));
  cout << c[1] << '\n';
}
0