結果

問題 No.407 鴨等素数間隔列の数え上げ
ユーザー togari_takamoto
提出日時 2016-08-05 22:40:44
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 99 ms
コード長 833 Byte
コンパイル時間 1,560 ms
使用メモリ 7,892 KB
最終ジャッジ日時 2018-07-18 18:27:37

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample_01.txt AC 3 ms
1,540 KB
sample_02.txt AC 3 ms
1,540 KB
sample_03.txt AC 2 ms
1,540 KB
sample_04.txt AC 12 ms
2,196 KB
sample_05.txt AC 3 ms
1,536 KB
system_test1.txt AC 92 ms
7,360 KB
system_test2.txt AC 49 ms
4,724 KB
test_1_01.txt AC 3 ms
1,552 KB
test_1_02.txt AC 2 ms
1,536 KB
test_1_03.txt AC 3 ms
1,552 KB
test_1_04.txt AC 3 ms
1,560 KB
test_1_05.txt AC 3 ms
1,536 KB
test_2_01.txt AC 3 ms
1,612 KB
test_2_02.txt AC 3 ms
1,572 KB
test_2_03.txt AC 3 ms
1,604 KB
test_2_04.txt AC 2 ms
1,544 KB
test_2_05.txt AC 3 ms
1,556 KB
test_2_06.txt AC 3 ms
1,560 KB
test_2_07.txt AC 3 ms
1,556 KB
test_3_01.txt AC 12 ms
2,220 KB
test_3_02.txt AC 30 ms
3,404 KB
test_3_03.txt AC 15 ms
2,344 KB
test_3_04.txt AC 13 ms
2,140 KB
test_3_05.txt AC 20 ms
2,608 KB
test_3_06.txt AC 30 ms
3,404 KB
test_3_07.txt AC 48 ms
4,724 KB
test_3_08.txt AC 48 ms
4,720 KB
test_3_09.txt AC 10 ms
2,024 KB
test_3_10.txt AC 22 ms
2,872 KB
test_3_11.txt AC 47 ms
4,456 KB
test_3_12.txt AC 11 ms
2,136 KB
test_3_13.txt AC 39 ms
3,932 KB
test_3_14.txt AC 47 ms
4,724 KB
test_4_01.txt AC 99 ms
7,892 KB
test_4_02.txt AC 98 ms
7,892 KB
test_4_03.txt AC 88 ms
7,096 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;

#define REP(i,n) for(ll i = 0; i < (n); ++i)

vb eratosthenes(ll n) {
	vb t(n + 1, true); t[0] = t[1] = false;
	for (ll i = 2; i <= n; ++i) if (t[i]) {
		for (ll j = 2 * i; j <= n; j += i) t[j] = false;
	}
	return t;
}

vl compress(const vb & t) {
	vl v; v.reserve((ll)(1.2 * t.size() / log(t.size())));
	REP(i, t.size()) if (t[i]) v.push_back(i);
	return v;
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);
	ll n, l; cin >> n >> l;
	auto ps = compress(eratosthenes(l));
	ll sum = 0;
	for (ll p : ps) {
		ll rest = l - p * (n - 1);
		if (rest < 0) break;
		sum += rest + 1;
	}
	cout << sum << endl;
	return 0;
}
0