Submission #467734

#	Time	Username	Problem	Language	Result	Execution time	Memory
467734		Neos	Savrsen (COCI17_savrsen)	C++14	0 / 120	132 ms	86968 KiB

savrsen

#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() {
#ifndef ONLINE_JUDGE
  freopen(task".inp", "r", stdin);
  freopen(task".out", "w", stdout);
#endif
  fastIO;

  sieve();
  cin >> a >> b;
  ll ans = 0;
  forw(i, a, b + 1) {
  	ans += abs(i - get(i));
  }
  cout << ans << endl;
}

Compilation message (stderr)

savrsen.cpp: In function 'int main()':
savrsen.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
savrsen.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 120