Advertisement
ivnikkk

Untitled

May 26th, 2022
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. const ll N = 5e6 + 1;
  10. ll O[N], O_pref[N];
  11. constexpr ll BITSIZE = 5e6 + 1;
  12. bitset<BITSIZE> prime;
  13. signed main() {
  14. //#ifdef _DEBUG
  15.     //freopen("input.txt", "r", stdin);
  16.     //freopen("output.txt", "w", stdout);
  17. //#endif
  18.     freopen("lrsigma.in", "r", stdin);
  19.     freopen("lrsigma.out", "w", stdout);
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(nullptr);
  22.     cout.tie(nullptr);
  23.     prime[0] = 1, prime[1] = 1;
  24.     O[0] = 0;
  25.     O[1] = 1;
  26.     for (ll i = 2; i < N; i++) {
  27.         if (!prime[i]) {
  28.             O[i] = 1 + i;
  29.             for (ll j =  2 * i; j < N; j += i) {
  30.                 prime[j] = 1;
  31.                 ll sum = 1;
  32.                 ll d = j;
  33.                 ll pw = 1;
  34.                 while (d % i == 0) {
  35.                     d /= i;
  36.                     pw *= i;
  37.                     sum += pw;
  38.                 }
  39.                 O[j] = O[j / pw] * sum;
  40.             }
  41.         }
  42.     }
  43.     O_pref[0] = 0;
  44.     for (ll i = 1; i < N; i++) {
  45.         O_pref[i] = O_pref[i - 1] + O[i];
  46.     }
  47.     ll l;
  48.     while (cin >> l) {
  49.         ll r;
  50.         cin >> r;
  51.         l--;
  52.         cout << O_pref[r] - O_pref[l] << '\n';
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement