結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2022-11-08 22:54:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 333 ms / 3,000 ms |
コード長 | 3,029 bytes |
コンパイル時間 | 5,229 ms |
コンパイル使用メモリ | 260,068 KB |
最終ジャッジ日時 | 2025-02-08 19:15:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll=long long; using ld=long double; ll inf=999999999999999999; ll mod=1000000007 ; // エラトステネスの篩 struct Eratosthenes { // テーブル vector<bool> isprime; // 整数 i を割り切る最小の素数 vector<ll> minfactor; vector<ll>mobius; // コンストラクタで篩を回す Eratosthenes(ll N) : isprime(N+1, true), minfactor(N+1, -1), mobius(N+1,1) { // 1 は予めふるい落としておく isprime[1] = false; minfactor[1] = 1; // 篩 for (ll p = 2; p <= N; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p についての情報更新 minfactor[p] = p; mobius[p]=-1; // p 以外の p の倍数から素数ラベルを剥奪 for (ll q = p * 2; q <= N; q += p) { // q は合成数なのでふるい落とす isprime[q] = false; // q は p で割り切れる旨を更新 if (minfactor[q] == -1) minfactor[q] = p; if ((q / p) % p == 0) mobius[q] = 0; else mobius[q] = -mobius[q]; } } } // 高速素因数分解 // pair (素因子, 指数) の vector を返す vector<pair<ll,ll>> factorize(ll n) { vector<pair<ll,ll>> res; while (n > 1) { ll p = minfactor[n]; ll exp = 0; // n で割り切れる限り割る while (minfactor[n] == p) { n /= p; ++exp; } res.emplace_back(p, exp); } return res; } vector<ll>divisors(ll n){ vector<ll>res({1}); auto pf=factorize(n); for (auto p : pf) { ll s=(ll)res.size(); for (ll i = 0; i < s; i++) { ll v=1; for (ll j = 0; j < p.second; j++) { v*=p.first; res.push_back(res[i]*v); } } } return res; } }; int main(){ ll n; cin >> n; Eratosthenes er(n*5+1); vector<ll>a(n+1,0); for (ll i = 2; i <=n; i++) { if (er.isprime[i]) { a[i]=1; } } vector<ll>b; b=convolution_ll(a,a); vector<ll>c=convolution_ll(b,a); vector<ll>e(n*2+1,0); for (ll i = 1; i <=n ;i++) { if (er.isprime[i]) { e[i*2]=1; } } vector<ll>d=convolution(a,e); ll ans=0; for (ll i = 2; i <c.size(); i++) { if (er.isprime[i]) { ans+=c[i]; if (i<d.size()) { ans-=d[i]*3; } } } cout << ans/6 << endl; }