Submission #67559910

---

Source Code Expand

//#pragma GCC optimize("O3")
//#pragma GCC optimization("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define endl '\n'
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ext exit(0)
#define INF 1000000000000000000
#define DIMBIT 32
#define fsort(a) sort(a.begin(), a.end())
#define fsortc(a, b) sort(a.begin(), a.end(), b)
#define pb push_back
#define frev(a) reverse(a.begin(), a.end())
#define fr first
#define se second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef pair<ll, ll> llpair;
#define ull unsigned long long
typedef pair<ll, ull> upair;
#define sz(a) int(a.size())
#define ld long double
#define db double
#define vll vector<ll>
#define all(x) x.begin(), x.end()
#define cnt_bit(a) __popcount(static_cast<unsigned long long>(a))
#define vint vector<int>
#define FOR(i, x, n) for(ll i = x; i < n; ++i)
#define rz resize
#define DIM 10000007
mt19937 rng(1488);

ll l,r, o = 1;

vll resheto() {
    bitset<DIM> pr;
    vll p;
    pr[0] = pr[1] = 1;
    FOR(i, 2, DIM) {
        if (!pr[i]) {
            p.pb(i);
            for (ll j = i*i; j < DIM; j+=i) {
                pr[j] = 1;
            }
        }
    }
    return p;
}

int main() {
    speed;
    cin >> l >> r;
    vll p = resheto();
    unordered_set<ll> st;
    for (auto &i: p) {
        for (ll j = (l/i + 1)*i; j <= r; j+=i) {
            if (st.find(j) != st.end()) continue;
            st.insert(j);
            ll x = j;
            while (x % i == 0) x/=i;
            if (x == 1) ++o;
        }
    }
    cout << o+r-l - sz(st) << endl;
    return 0;
}

Submission Info

Judge Result