結果

問題 No.732 3PrimeCounting
ユーザー narushimasnarushimas
提出日時 2021-06-06 02:47:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,567 bytes
コンパイル時間 4,011 ms
コンパイル使用メモリ 258,688 KB
最終ジャッジ日時 2025-01-22 03:47:04
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 68 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  rep1(i, N){
    if(era.isPrime(i)) ps.pb(i);
  }
  debug(ps);
  vv<int> dp(3 * N , vi(4));
  dp[0][0] = 1;
  for(int p : ps){
    rrep(j, 3){
      int nj = j + 1;
      rep(i, 3 * N){
        int ni = i + p;
        if(ni >= 3 * N) break;
        dp[ni][nj] += dp[i][j];
      }
    }
  }
  debug(dp);
  ll ans = 0;
  rep(i, 3 * N){
    if(era.isPrime(i)){
      debug(i, dp[i][3]);
      ans += dp[i][3];
    }
  }
  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;
}
0