結果

問題 No.917 Make One With GCD
ユーザー risujirohrisujiroh
提出日時 2019-10-25 21:56:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,300 bytes
コンパイル時間 2,228 ms
コンパイル使用メモリ 176,844 KB
実行使用メモリ 814,608 KB
最終ジャッジ日時 2024-07-23 20:33:40
合計ジャッジ時間 5,703 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
}

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

constexpr int L = 1e8;

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