結果

問題 No.917 Make One With GCD
ユーザー risujirohrisujiroh
提出日時 2019-10-25 21:57:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,331 bytes
コンパイル時間 2,159 ms
コンパイル使用メモリ 185,196 KB
実行使用メモリ 42,000 KB
最終ジャッジ日時 2024-07-23 20:38:41
合計ジャッジ時間 19,650 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 437 ms
41,260 KB
testcase_04 AC 437 ms
40,740 KB
testcase_05 AC 436 ms
40,820 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 437 ms
41,568 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 435 ms
40,320 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 436 ms
41,024 KB
testcase_22 AC 433 ms
41,556 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 433 ms
40,532 KB
testcase_29 AC 436 ms
40,372 KB
testcase_30 AC 435 ms
41,512 KB
testcase_31 WA -
testcase_32 AC 436 ms
40,148 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 438 ms
41,668 KB
権限があれば一括ダウンロードができます

ソースコード

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

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

constexpr int L = 1e8;

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;
  }
  ifmult(c, sieve(L));
  cout << c[1] << '\n';
}
0