raw source code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

/// --- modulo Library {{{ ///
ll extgcd(ll a, ll b, ll& x, ll& y) {
  if(b==0) {
    x = 1; y = 0;
    return a;
  }
  ll d = extgcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}
ll modpow(ll a, ll b, ll mod = 1e9 + 7) {
  a = (a % mod + mod) % mod;
  ll r = 1;
  while(b){
    if(b & 1) r = r * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return r;
}
ll modinv(ll a, ll mod = 1e9 + 7) {
  a = (a % mod + mod) % mod;
  ll x = 0, y = 0;
  extgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}
/// }}}--- ///

// require modulo library
/// NTT Library {{{ ///
struct NTT {
  ll mod, primitive;
  NTT() {}
  NTT(ll mod, ll primitive): mod(mod), primitive(primitive) {}
  vector<ll> fft(vector<ll> a, bool inv = 0) {
    int n = a.size();
    int h = 32 - __builtin_clz(n); h--;
    // bitの反転
    for(int i = 0; i < n; i++) {
      int j = 0;
      for(int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);
      if(i < j) swap(a[i], a[j]);
    }
    // i : 今考えている多項式の次数 / 2
    for(int i = 1; i < n; i *= 2) {
      ll zeta = modpow(primitive, (mod - 1) / (i * 2), mod);
      if(inv) zeta = modinv(zeta, mod);
      ll tmp = 1;
      // j : 指数
      for(int j = 0; j < i; j++) {
        // k : 何個目の多項式か
        for(int k = 0; k < n; k += i * 2) {
          ll s = a[k + j + 0];
          ll t = a[k + j + i] * tmp % mod;
          a[k + j + 0] = (s + t) % mod;
          a[k + j + i] = (s - t) % mod;
        }
        tmp = tmp * zeta % mod;
      }
    }
    int invn = modinv(n, mod);
    if(inv) for(int i = 0; i < n; i++) a[i] = a[i] * invn % mod;
    for(int i = 0; i < n; i++) a[i] = (a[i] + mod) % mod;
    return a;
  }
  template<typename T> vector<ll> conv(vector<T> aa, vector<T> bb) {
    int deg = aa.size() + bb.size();
    int n = 1;
    while(n < deg) n <<= 1;
    vector<ll> a(n), b(n);
    for(int i = 0; i < (int) aa.size(); i++) a[i] = aa[i] % mod;
    for(int i = 0; i < (int) bb.size(); i++) b[i] = bb[i] % mod;
    a = fft(a); b = fft(b);
    vector<ll> c(n);
    for(int i = 0; i < n; i++) c[i] = a[i] * b[i] % mod;
    return fft(c, 1);
  }
};
/// }}}--- ///

vector<NTT> ntts {
  NTT((1 << 24) * 73 + 1, 3), NTT((1 << 21) * 3 * 7 * 23 + 1, 5),
    NTT((1 << 25) * 5 + 1, 3), NTT((1 << 26) * 7 + 1, 3),
    NTT((1 << 21) * 3 * 3 * 7 * 7 + 1, 5),
};

// require garner library when use more than 2 ntt
ll garner(vector<ll> n, vector<ll> mods, ll mod);
template<typename T>
vector<ll> conv(vector<T> a, vector<T> b, int use = 1, ll mod = 1e9 + 7) {
  vector< vector<ll> > cs;
  auto nlist = ntts;
  nlist.resize(use);
  for(auto ntt : nlist) {
    cs.emplace_back(ntt.conv(a, b));
  }
  if(use == 1) return cs[0];
  int n = cs[0].size();
  vector<ll> c(n);
  for(int i = 0; i < n; i++) {
    vector<ll> vals(use), mods(use);
    for(int j = 0; j < use; j++) {
      vals[j] = cs[j][i];
      mods[j] = nlist[j].mod;
    }
    c[i] = garner(vals, mods, mod);
  }
  return c;
}

// require mods library
/// Garner Library {{{ ///
ll garner(vector<ll> n, vector<ll> mods, ll mod){
  n.emplace_back(0);
  mods.emplace_back(mod);
  vector<ll> coeffs(n.size(), 1); // v_i の係数
  vector<ll> constants(n.size(), 0); // v_i の項より後ろの項の和,答え mod mods[i]
  for(int i = 0; i < (int) n.size(); i++) {
    // coeffs[i] * v_i + constants[i] == n[i] (mod mods[i]) を解く
    ll v = (n[i] - constants[i]) * modinv(coeffs[i], mods[i]) % mods[i];
    if (v < 0) v += mods[i];
    for (int j = i + 1; j < (int) n.size(); j++) {
      // coeffs[j] is (mod j)
      (constants[j] += coeffs[j] * v) %= mods[j];
      (coeffs[j] *= mods[i]) %= mods[j];
    }
  }
  return constants.back();
}
/// }}}--- ///

// FFTで殴る
// 配列の大きさ間違ってたノエー(WA_RE)
// 桁数足りてなかった, うしー
// のえるちゃんを選ぶな, るましを選べ
// さすがにあってると思うが
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  vector<int> ecasdqina(2e5 + 1);
  int c1 = 0;
  for(int i = 0; i < n; i++) {
    int x; cin >> x;
    ecasdqina[x]++;
    if(x == 1) c1++;
  }
  auto noel = conv(ecasdqina, ecasdqina, 2, 4e10 + 100);
  vector<int> primes;
  ll ans = 0;
  for(int i = 2; i <= int(4e5); i++) {
    int flag = 1;
    for(int p : primes) {
      if((ll) p * p > i) break;
      if(i % p == 0) {
        flag = 0;
        break;
      }
    }
    if(flag) {
      primes.emplace_back(i);
      ll res = noel[i];
      if(i == 2) res -= c1;
      res /= 2;
      ans += res;
    }
  }
  cout << ans << endl;
}
# ユーザ名 問題 言語 状態 得点 提出日時
00282 るまし 0025 - のえるちゃん選び C++11 AC 15 18-03-25 06:21

セット

# セット 得点 Cases
1 ALL 15 / 15 *

テストケース

テストケース取得

ファイル名 状態 実行時間 メモリ使用量 #
random_01.txt AC 3850 ms 28312 KB 1
random_02.txt AC 3660 ms 28312 KB 1
random_03.txt AC 3810 ms 28308 KB 1
random_04.txt AC 3810 ms 28312 KB 1
random_05.txt AC 3810 ms 28312 KB 1
random_06.txt AC 3810 ms 28308 KB 1
random_07.txt AC 3840 ms 28460 KB 1
random_08.txt AC 3770 ms 28312 KB 1
random_09.txt AC 3910 ms 28312 KB 1
random_10.txt AC 3620 ms 28308 KB 1
random_11.txt AC 3770 ms 28308 KB 1
random_12.txt AC 3760 ms 28312 KB 1
random_13.txt AC 3650 ms 28312 KB 1
random_14.txt AC 3930 ms 28312 KB 1
random_15.txt AC 3700 ms 28308 KB 1
random_16.txt AC 3610 ms 28312 KB 1
random_17.txt AC 3690 ms 28308 KB 1
sample_01.txt AC 3620 ms 28304 KB 1
sample_02.txt AC 3670 ms 28308 KB 1
sample_03.txt AC 3830 ms 28396 KB 1