結果

問題 No.1661 Sum is Prime (Hard Version)
コンテスト
ユーザー 🍮かんプリン
提出日時 2021-08-30 12:02:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 46 ms / 3,000 ms
コード長 1,681 bytes
コンパイル時間 4,286 ms
コンパイル使用メモリ 165,456 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 16:58:19
合計ジャッジ時間 3,759 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2021.08.30 12:02:38
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;


ll prime_cnt(const ll N) {
	if (N <= 1) return 0;
	if (N == 2) return 1;
	const int sq = (int)sqrtl(N);
	int s = (1+sq)/2;
	vector<int> smalls(s); iota(smalls.begin(), smalls.end(),0); 
	vector<int> roughs(s); for (int i = 0; i<s;i++) roughs[i] = 2*i+1;
	vector<ll> larges(s); for (int i = 0; i<s;i++) larges[i] = (N/(2*i+1)-1)/2;
	vector<bool> skip(sq+1);
	auto divide = [&](ll n, ll d) { return int((double)n/d); };
	auto half = [&](int n) { return (n-1)/2; };
	int pc = 0;
	for (int p = 3; p <= sq; p += 2) if (!skip[p]) {
		int q = p*p; if ((ll)q*q > N) break;
		skip[p] = 1; for (int i = q; i <= sq; i += 2*p) skip[i] = 1;
		int ns = 0;
		for (int k = 0; k < s; k++) {
			int i = roughs[k]; if (skip[i]) continue;
			ll d = (ll)i*p;
			larges[ns] = larges[k]+pc;
			larges[ns] -= d <= sq ? larges[smalls[d/2]-pc] : smalls[half(divide(N,d))];
			roughs[ns++] = i;
		}
		s = ns;
		for (int i = half(sq), j = (sq/p-1)|1; j >= p; j -= 2) {
			int c = smalls[j/2]-pc;
			for (int e = j*p/2; i >= e; --i) smalls[i] -= c;
		}
		++pc;
	} 
	for (int k = 1; k < s; k++) larges[0] -= larges[k]; 
	larges[0] += (ll)(s+2*(pc-1))*(s-1)/2;
	for (int l = 1;l < s;l++) {
		int q = roughs[l]; ll m = N/q;
		int e = smalls[half(int(m/q))]-pc; if (e <= l) break;
		for(int k = l+1; k < e+1; k++) larges[0] += smalls[half(divide(m,roughs[k]))];
		larges[0] -= (ll)(e-l)*(pc+l-1);
	}
	return larges[0]+1;
}
int main() {
    ll l,r;cin >> l >> r;
    cout << prime_cnt(r)-prime_cnt(l-1)+prime_cnt(2*r)-prime_cnt(2*l) << endl;
    return 0;
}
0