oj.uz

Submission #467735

# Submission time Handle Problem Language Result Execution time Memory
467735 2021-08-24T08:56:32 Z Neos Savrsen (COCI17_savrsen) C++14
120 / 120
 701 ms 86936 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
 
#define task "HHH"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define all(x) x.begin(), x.end()
#define numBit(x) __builtin_popcount(x)
#define lb lower_bound
#define ub upper_bound
#define ar array
#define endl '\n'
 
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
 
const int N = 1e7 + 7;
const ll inf = 1e9;
 
int a, b;
vll p, spf;
 
void sieve() {
  p.assign(1, 2);
  spf.assign(N+1, 2);
  spf[1] = 1;
  for (int i = 3; i <= N; i += 2) {
    if (spf[i] == 2) p.pb(spf[i] = i);
    for (int j = 0; j < sz(p) && p[j] <= spf[i] && p[j] * i <= N; j++)
      spf[p[j] * i] = p[j];
  }
}
 
ll fexp(ll x, ll y) {
  ll ans = 1;
  while (y > 0) {
    if (y & 1) ans = ans * x;
    x = x * x;
    y >>= 1;
  }
  return ans;
}
 
ll get(ll x) {
  ll ans = 1, tmp = x;
  while (x > 1) {
    ll p = spf[x], cnt = 0;
    do {
      x /= p, ++cnt;
    } while (p == spf[x]);
    ans *= (fexp(p, cnt + 1) - 1) / (p - 1);
  }
  if (x != 1) ans *= (fexp(x, 2) - 1) / (x - 1);
  return ans - tmp;
}
 
int main() {
  fastIO;
 
  sieve();
  cin >> a >> b;
  ll ans = 0;
  forw(i, a, b + 1) {
  	ans += abs(i - get(i));
  }
  cout << ans << endl;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 86860 KB Output is correct
2 Correct 110 ms 86828 KB Output is correct
3 Correct 116 ms 86904 KB Output is correct
4 Correct 112 ms 86840 KB Output is correct
5 Correct 664 ms 86904 KB Output is correct
6 Correct 701 ms 86840 KB Output is correct
7 Correct 656 ms 86840 KB Output is correct
8 Correct 249 ms 86936 KB Output is correct