#961930 (C++14) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	こうき
提出日時	2024-03-19 23:34:05
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	422 ms / 3,000 ms
コード長	5,092 bytes
コンパイル時間	3,648 ms
コンパイル使用メモリ	178,700 KB
実行使用メモリ	23,624 KB
最終ジャッジ日時	2024-03-19 23:34:18
合計ジャッジ時間	12,685 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4 ms 6,548 KB
testcase_01	AC	4 ms 6,548 KB
testcase_02	AC	4 ms 6,548 KB
testcase_03	AC	4 ms 6,548 KB
testcase_04	AC	4 ms 6,548 KB
testcase_05	AC	4 ms 6,548 KB
testcase_06	AC	4 ms 6,548 KB
testcase_07	AC	4 ms 6,548 KB
testcase_08	AC	4 ms 6,548 KB
testcase_09	AC	4 ms 6,548 KB
testcase_10	AC	4 ms 6,548 KB
testcase_11	AC	5 ms 6,548 KB
testcase_12	AC	4 ms 6,548 KB
testcase_13	AC	4 ms 6,548 KB
testcase_14	AC	4 ms 6,548 KB
testcase_15	AC	4 ms 6,548 KB
testcase_16	AC	4 ms 6,548 KB
testcase_17	AC	4 ms 6,548 KB
testcase_18	AC	4 ms 6,548 KB
testcase_19	AC	4 ms 6,548 KB
testcase_20	AC	6 ms 6,548 KB
testcase_21	AC	10 ms 6,548 KB
testcase_22	AC	10 ms 6,548 KB
testcase_23	AC	5 ms 6,548 KB
testcase_24	AC	5 ms 6,548 KB
testcase_25	AC	17 ms 6,628 KB
testcase_26	AC	14 ms 6,548 KB
testcase_27	AC	6 ms 6,548 KB
testcase_28	AC	6 ms 6,548 KB
testcase_29	AC	9 ms 6,548 KB
testcase_30	AC	9 ms 6,548 KB
testcase_31	AC	10 ms 6,548 KB
testcase_32	AC	15 ms 6,568 KB
testcase_33	AC	15 ms 6,568 KB
testcase_34	AC	15 ms 6,568 KB
testcase_35	AC	14 ms 6,548 KB
testcase_36	AC	14 ms 6,548 KB
testcase_37	AC	5 ms 6,548 KB
testcase_38	AC	5 ms 6,548 KB
testcase_39	AC	14 ms 6,548 KB
testcase_40	AC	10 ms 6,548 KB
testcase_41	AC	10 ms 6,548 KB
testcase_42	AC	10 ms 6,548 KB
testcase_43	AC	10 ms 6,548 KB
testcase_44	AC	10 ms 6,548 KB
testcase_45	AC	7 ms 6,548 KB
testcase_46	AC	6 ms 6,548 KB
testcase_47	AC	9 ms 6,548 KB
testcase_48	AC	17 ms 6,768 KB
testcase_49	AC	17 ms 6,768 KB
testcase_50	AC	10 ms 6,548 KB
testcase_51	AC	10 ms 6,548 KB
testcase_52	AC	7 ms 6,548 KB
testcase_53	AC	31 ms 7,620 KB
testcase_54	AC	204 ms 15,528 KB
testcase_55	AC	207 ms 15,528 KB
testcase_56	AC	204 ms 15,528 KB
testcase_57	AC	63 ms 9,396 KB
testcase_58	AC	60 ms 9,396 KB
testcase_59	AC	32 ms 7,656 KB
testcase_60	AC	97 ms 10,548 KB
testcase_61	AC	97 ms 10,548 KB
testcase_62	AC	213 ms 16,996 KB
testcase_63	AC	121 ms 12,428 KB
testcase_64	AC	101 ms 11,204 KB
testcase_65	AC	101 ms 11,200 KB
testcase_66	AC	5 ms 6,548 KB
testcase_67	AC	5 ms 6,548 KB
testcase_68	AC	215 ms 16,104 KB
testcase_69	AC	206 ms 16,104 KB
testcase_70	AC	204 ms 15,564 KB
testcase_71	AC	204 ms 15,564 KB
testcase_72	AC	120 ms 12,180 KB
testcase_73	AC	259 ms 20,156 KB
testcase_74	AC	269 ms 20,156 KB
testcase_75	AC	17 ms 6,620 KB
testcase_76	AC	207 ms 16,036 KB
testcase_77	AC	62 ms 9,488 KB
testcase_78	AC	249 ms 18,288 KB
testcase_79	AC	206 ms 16,272 KB
testcase_80	AC	253 ms 17,556 KB
testcase_81	AC	204 ms 15,604 KB
testcase_82	AC	7 ms 6,548 KB
testcase_83	AC	62 ms 9,448 KB
testcase_84	AC	95 ms 9,936 KB
testcase_85	AC	203 ms 14,800 KB
testcase_86	AC	248 ms 17,760 KB
testcase_87	AC	422 ms 23,624 KB
testcase_88	AC	415 ms 23,624 KB

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

ソースコード

raw source code

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
#include <random>
#include <stdio.h>
#include <math.h>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#include <atcoder/all>
using namespace std;


typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vl;
typedef vector<vl> ml;
typedef vector<vector<int>> mati;
typedef vector<vector<ll>> matl;
// typedef pair<ll, ll> P;
// typedef pair<P, P> PP;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define itrrep(itr, s) for(auto itr=s.begin(); itr!=s.end(); itr++)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define len(x) ((ll)(x).size())
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define rvs(x) reverse(all(x))
#define lb(x, v) lower_bound(all(x), v)
const ll INFL = 1LL<<60;
const ll INF = 1LL<<30;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
double EPS = 1e-10;
const double PI=3.1415926535897932384626433832795028841971;
vector<ll>dy={0,1,0,-1,1,1,-1,-1,0};
vector<ll>dx={1,0,-1,0,1,-1,1,-1,0};

// for debug
template<typename __T__>
void put(__T__ x){cout<<x;}
template<typename __T__, typename __U__>
void put(pair<__T__ , __U__> x){put("{");put(x.f);put(", ");put(x.s);put("}");}
template<typename __T__>
void put(vector<__T__> x){put("[");rep(i,len(x)){put(x[i]);if(i!=len(x)-1)put(", ");}put("]");}
template<typename __T__>
void put(set<__T__> x){put("{");auto itr=x.begin();while(itr!=x.end()){put(*itr);itr++;if(itr!=x.end()){put(",  ");}}put("}");}
template<typename __T__, typename __U__>
void put(map<__T__, __U__> x){put("{");auto itr=x.begin();while(itr!=x.end()){put(itr->f);put("->");put(itr->s);itr++;if(itr!=x.end()){put(",  ");}}put("}");}
void print(){cout<<endl;}
template <class Head>
void print(Head&& head){put(head);cout<<endl;}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){put(head);put(" ");print(std::forward<Tail>(tail)...);}
#define debug(x) cout<<#x<<": ";print(x);
// io util
template<typename __T__>
void vecin(vector<__T__>& x){rep(i, len(x)){cin>>x[i];}}
template<typename __T__>
void matin(vector<vector<__T__>>& x){rep(i,len(x))rep(j,len(x[i])){cin>>x[i][j];}}
template<typename __T__>
void vecout(vector<__T__> x){rep(i,len(x)){cout<<x[i];if(i!=len(x)-1)cout<<" ";}cout<<endl;}
template<typename __T__>
void matout(vector<vector<__T__>> x){rep(i,len(x)){vecout(x[i]);}}
template<typename __T__>
void output(__T__ x){cout << x << endl;}
void input(){}
template <class Head, class... Tail>
void input(Head&& head, Tail&&... tail){cin>>head;input(forward<Tail>(tail)...);}
// util
template<typename __T__>
vector<__T__> to_unique(vector<__T__> x){sort(all(x));x.erase(unique(all(x)), x.end());return x;}
void pres(double A){cout<<setprecision(32)<<A<<endl;}
void BinaryPrint(ll x,ll y=8){rep(i,y)cout<<(x>>(y-1-i)&1);cout<<endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}
ll pow_long(ll x,ll k){ll res=1;while(k>0){if(k%2)res*=x;x*=x;k/=2;}return res;}
ll pow_mod(ll x,ll k,ll _mod=MOD){ll res=1;while(k>0){if(k%2){res*=x;res%=_mod;}x*=x;x%=_mod;k/=2;}res%=_mod;return res;}
ll inverse(ll x,ll _mod=MOD){return pow_mod(x,MOD-2,_mod);};
ll gcd(ll a,ll b){if(b==0){return a;}return gcd(b,a%b);}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;};
ll digit(ll A,ll d=10){ll res=0;while(A){res++;A/=d;}return res;}
ll str2ll(string s){ll res=0;rep(i,len(s)){res=res*10+s[i]-'0';}return res;}
ll str2llmod(string s,ll mod=MOD){ll res=0;rep(i,len(s)){res=(res*10+s[i]-'0')%mod;}return res;}
string ll2str(ll x){if(x==0)return "0";string res;ll d=digit(x);rep(i,digit(x)){res+='0'+x/pow_long(10,d-1-i)%10;}return res;}

// c++ -std=gnu++14 a.cpp
// g++ a.cpp -Wno-unqualified-std-cast-call -std=c++14 -I .
// #include <atcoder/all>

//エラトステネスの篩O(n);
ll prime[300010];//i番目の素数
bool is_prime[300011];
//n以下の素数の個数を全て返す関数
ll sieve(ll n){
    ll p = 0;
    for(ll i = 0; i <= n; i++) is_prime[i] = true;
    is_prime[0] = false;
    is_prime[1] = false;
    for(ll i = 2; i <= n; i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;
        }
    }
    return p;
}


void solve(){
  sieve(300010);
  ll N;
  cin >> N;
  vector<ll> A(N+1, 0), A2(2*N+1, 0);
  rep(i, N+1)if(is_prime[i]) A[i]++;
  rep(i, N+1)if(is_prime[i]) A2[i*2]++;
  vector<ll> B = atcoder::convolution_ll(A, A);
  vector<ll> C = atcoder::convolution_ll(B, A);
  vector<ll> C2 = atcoder::convolution_ll(A2, A);
  ll ans = 0;
  rep(i, 3*N+1)if(is_prime[i]) ans += C[i];
  rep(i, 3*N+1)if(is_prime[i]) ans -= C2[i] * 3;
  ans /= 6;
  print(ans);
}



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}

yukicoder

結果

テストケース

ソースコード