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

/// --- modulo Library {{{ ///
constexpr 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;
}
constexpr 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;
}
constexpr 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;
}
template<int N, int mod = 1e9 + 7> struct Factorial {
  int arr[N+1], inv[N+1];
  int operator[](int i) const { return arr[i]; }
  constexpr Factorial(): arr(), inv() {
    arr[0] = 1;
    for(int i = 1; i <= N; i++) {
      arr[i] = (ll) i * arr[i - 1] % mod;
    }
    inv[N] = modinv(arr[N], mod);
    for(int i = N-1; i >= 0; i--) {
      inv[i] = (ll) (i + 1) * inv[i + 1] % mod;
    }
  }
  int C(int n, int r) {
    if(n < 0 || r < 0 || n < r) return 0;
    return modmul(arr[n], modmul(inv[r], inv[n - r], mod), mod);
  }
};
/// }}}--- ///

// constexpr int N = 1e5 + 10;
// constexpr Factorial<N> fact;

// 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で殴る
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  vector<int> a(2e4 + 1);
  int c1 = 0;
  for(int i = 0; i < n; i++) {
    int x; cin >> x;
    a[x]++;
    if(x == 1) c1++;
  }
  auto c = conv(a, a);
  vector<int> primes;
  ll ans = 0;
  for(int i = 2; i <= int(4e4); i++) {
    int flag = 1;
    for(int p : primes) {
      if(p * p > i) break;
      if(i % p == 0) {
        flag = 0;
        break;
      }
    }
    if(flag) {
      primes.emplace_back(i);
      ll res = c[i];
      if(i == 2) res -= c1;
      res /= 2;
      ans += res;
    }
  }
  cout << ans << endl;
}
./Main.cpp: In function 'constexpr ll extgcd(ll, ll, ll&, ll&)':
./Main.cpp:14:1: error: body of constexpr function 'constexpr ll extgcd(ll, ll, ll&, ll&)' not a return-statement
 }
 ^
./Main.cpp: In function 'constexpr ll modpow(ll, ll, ll)':
./Main.cpp:24:1: error: body of constexpr function 'constexpr ll modpow(ll, ll, ll)' not a return-statement
 }
 ^
./Main.cpp: In function 'constexpr ll modinv(ll, ll)':
./Main.cpp:30:1: error: body of constexpr function 'constexpr ll modinv(ll, ll)' not a return-statement
 }
 ^
./Main.cpp: In constructor 'Factorial<N, mod>::Factorial()':
./Main.cpp:43:3: error: constexpr constructor does not have empty body
   }
   ^
# ユーザ名 問題 言語 状態 得点 提出日時
00277 るまし 0025 - のえるちゃん選び C++11 CE 18-03-25 06:01

セット

# セット 得点 Cases

テストケース

テストケース取得

ファイル名 状態 実行時間 メモリ使用量 #