#694225 (C++11) No.1661 Sum is Prime (Hard Version)

• 問題: No.1661 Sum is Prime (Hard Version)
• ユーザー: 🍮かんプリン
• 提出日時: 2021-08-30 12:02:44
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 42 ms / 3,000 ms
• コード長: 1,681 bytes
• コンパイル時間: 1,673 ms
• コンパイル使用メモリ: 165,884 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-23 15:01:42
• 合計ジャッジ時間: 3,047 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	28 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	25 ms; 5,248 KB
testcase_13	AC	24 ms; 5,248 KB
testcase_14	AC	27 ms; 5,248 KB
testcase_15	AC	34 ms; 5,248 KB
testcase_16	AC	29 ms; 5,248 KB
testcase_17	AC	27 ms; 5,248 KB
testcase_18	AC	12 ms; 5,248 KB
testcase_19	AC	20 ms; 5,248 KB
testcase_20	AC	13 ms; 5,248 KB
testcase_21	AC	22 ms; 5,248 KB
testcase_22	AC	42 ms; 5,248 KB
testcase_23	AC	41 ms; 5,248 KB

ソースコード

/**
 *   @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;
}