#664272 (C++17) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	narushimas
提出日時	2021-06-06 16:33:30
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	553 ms / 3,000 ms
コード長	5,410 bytes
コンパイル時間	4,351 ms
コンパイル使用メモリ	267,840 KB
実行使用メモリ	7,168 KB
最終ジャッジ日時	2024-11-22 23:22:39
合計ジャッジ時間	11,260 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	3 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	3 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	3 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	2 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	3 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	2 ms 5,248 KB
testcase_45	AC	2 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	2 ms 5,248 KB
testcase_48	AC	3 ms 5,248 KB
testcase_49	AC	4 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	3 ms 5,248 KB
testcase_52	AC	2 ms 5,248 KB
testcase_53	AC	6 ms 5,248 KB
testcase_54	AC	115 ms 5,376 KB
testcase_55	AC	115 ms 5,376 KB
testcase_56	AC	117 ms 5,248 KB
testcase_57	AC	15 ms 5,248 KB
testcase_58	AC	15 ms 5,248 KB
testcase_59	AC	6 ms 5,248 KB
testcase_60	AC	23 ms 5,248 KB
testcase_61	AC	23 ms 5,248 KB
testcase_62	AC	175 ms 5,760 KB
testcase_63	AC	48 ms 5,248 KB
testcase_64	AC	30 ms 5,248 KB
testcase_65	AC	30 ms 5,248 KB
testcase_66	AC	2 ms 5,248 KB
testcase_67	AC	2 ms 5,248 KB
testcase_68	AC	139 ms 5,632 KB
testcase_69	AC	149 ms 5,632 KB
testcase_70	AC	124 ms 5,248 KB
testcase_71	AC	122 ms 5,376 KB
testcase_72	AC	43 ms 5,248 KB
testcase_73	AC	374 ms 6,528 KB
testcase_74	AC	375 ms 6,528 KB
testcase_75	AC	3 ms 5,248 KB
testcase_76	AC	144 ms 5,504 KB
testcase_77	AC	17 ms 5,248 KB
testcase_78	AC	247 ms 6,144 KB
testcase_79	AC	144 ms 5,632 KB
testcase_80	AC	216 ms 6,144 KB
testcase_81	AC	124 ms 5,504 KB
testcase_82	AC	2 ms 5,248 KB
testcase_83	AC	15 ms 5,248 KB
testcase_84	AC	18 ms 5,248 KB
testcase_85	AC	94 ms 5,248 KB
testcase_86	AC	221 ms 6,144 KB
testcase_87	AC	542 ms 7,168 KB
testcase_88	AC	553 ms 7,040 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) {}
#endif

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

#define ll long long
#define ld long double
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i, n) for(int i=1; i<=(n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define RFOR(i, a, b) for(int i=(b)-1; i>=(a); --i)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define popcnt(x) __builtin_popcountll(x)
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define newline puts("")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T>>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<ld>; 
using vs = vector<string>;
using vpii = vector<pii>;
using vpl = vector<pll>; 
using vpd = vector<pdd>;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
using int128 = __int128_t;
using mint = atcoder::modint1000000007;
const ll MOD = 1000000007;
// using mint = atcoder::modint998244353;
// const ll MOD = 998244353;
// using mint = atcoder::modint; //mint::set_mod(mod);

/** debug **/
template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(mint x) { return to_string(x.val()); } 
string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; }
template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; }
template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; }
template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; }
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }

#define endl '\n'
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const long double eps= 1e-10;
const long double PI = 3.141592653589793238462643383279502884L;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

struct EratosSieve {
  int n;
  vector<int> f, primes;
  EratosSieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> _factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<pair<int,int>> factorize(int x) {
    vector<int> fl = _factorList(x);
    if (fl.size() == 0) return {};
    vector<pair<int,int>> res(1, pair<int,int>(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
  vector<pair<ll,int>> factorize(ll x) {
    vector<pair<ll,int>> res;
    for (int p : primes) {
      int y = 0;
      while (x%p == 0) x /= p, ++y;
      if (y != 0) res.emplace_back(p,y);
    }
    if (x != 1) res.emplace_back(x,1);
    return res;
  }
};

void solve() {
  int N; cin >> N;
  EratosSieve era(3 * N);
  vi ps = era.primes;
  int M = sz(ps);
  
  vl dp(3 * N + 1);

  ll ans = 0;
  
  for(int i=0;ps[i] <= N;i++){
    int c = ps[i];
    FOR(j, i+1, M){
      int s = ps[j];
      ans += dp[s - c];
    }
    rep(j, i){
      dp[ps[j] + ps[i]]++;
    }
  }
  
  debug(dp);

  cout << ans << endl;
}

int main(){
  int tests = 1;
  // scanf("%d", &tests);
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(15);
  rep1(i, tests){
    solve();
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード