Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- const ll N = 5e6 + 1;
- ll O[N], O_pref[N];
- constexpr ll BITSIZE = 5e6 + 1;
- bitset<BITSIZE> prime;
- signed main() {
- //#ifdef _DEBUG
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- //#endif
- freopen("lrsigma.in", "r", stdin);
- freopen("lrsigma.out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- prime[0] = 1, prime[1] = 1;
- O[0] = 0;
- O[1] = 1;
- for (ll i = 2; i < N; i++) {
- if (!prime[i]) {
- O[i] = 1 + i;
- for (ll j = 2 * i; j < N; j += i) {
- prime[j] = 1;
- ll sum = 1;
- ll d = j;
- ll pw = 1;
- while (d % i == 0) {
- d /= i;
- pw *= i;
- sum += pw;
- }
- O[j] = O[j / pw] * sum;
- }
- }
- }
- O_pref[0] = 0;
- for (ll i = 1; i < N; i++) {
- O_pref[i] = O_pref[i - 1] + O[i];
- }
- ll l;
- while (cin >> l) {
- ll r;
- cin >> r;
- l--;
- cout << O_pref[r] - O_pref[l] << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement