AtCoder Beginner Contest 084 - D - 2017-like Number
素数が来たらとりあえず列挙しとけ
https://gyazo.com/afa7dc01f6545b436a208f7a53a54999
考えたこと
Q, L,Rが$ 10^5なので貪欲にやると間に合わない。計算量を落とす必要がある。
二分探索は使いそうだな..
予め2017に似た数のソート済み配列を作っておいて、それに対して、l,rでlower_boundとupper_boundとって、差分出せば個数わかるかな?
簡単にするために、l以上r以下の場合だけ考える
[1,2,3,5,9,10,15,20,24]という配列があって、l=4,r=16とするこれで、lでlower_boundを取ると5のイテレーターが、rでupper_boundを取ると、20のイテレーターが取れる。(lower_boundは以上, upper_boundはより大きい)
あとは、rの-1までが、条件を満たす範囲、これで差分を取れば個数がわかる.
次に2017に似た数を求める。
Nも(N+1)/2も素数という条件から、少なくとも全ての素数よりは数が少ないことはわかる。
見ないといけない最大の数は$ 10^5, 素数の列挙は$ O(N\sqrt N)なので、ギリまにあうかな
すべての素数を集めて、それを1つづつ見ていけばいいだろう($ 10^5よりは大きなならないはずだし)
探し方は、全ての素数をvectorに入れて、(vector[i]+1)/2がvectorに含まれるかをみる
C++の場合は、contains関数ないので、それっぽいの用意すること(これも二分探索で行けるのであまり計算量は考慮しなくて良いはず
これで必要なものが両方できたので、実装できる
提出したコード
code: D.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int N;
vector<int> P;
void prime(const int N) {
for(int i = 2; i <= N; i++) {
bool flag = true;
for(int j = 2; j * j <= i; j++) {
if(i % j == 0) {
flag = false;
break;
}
}
if(flag) P.emplace_back( i );
}
}
bool vector_finder(std::vector<int> vec, int number) {
auto itr = std::find(vec.begin(), vec.end(), number);
size_t index = std::distance( vec.begin(), itr );
if (index != vec.size()) { // 発見できたとき
return true;
}
else { // 発見できなかったとき
return false;
}
}
int main() {
// 前準備
prime(100000 + 5);
vector<int> near_2017;
rep(i, P.size()-1) {
if(vector_finder(P, ((Pi+1)/2))) near_2017.push_back(Pi); }
int q; cin >> q;
rep(i, q) {
int l, r; cin >> l >> r;
auto l_itr = lower_bound(near_2017.begin(), near_2017.end(), l);
auto r_itr = upper_bound(near_2017.begin(), near_2017.end(), r);
auto l_idx = l_itr - near_2017.begin();
auto r_idx = r_itr - near_2017.begin() - 1; // upper_boundはぎり満たさないやつなので
cout << r_idx - l_idx + 1 << endl;
}
return 0;
}