Submission #1109417

#TimeUsernameProblemLanguageResultExecution timeMemory
1109417_callmelucianSavrsen (COCI17_savrsen)C++14
120 / 120
212 ms62312 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e7 + 7;
int sumFactor[mn], vp[mn];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int l, r; cin >> l >> r;
    for (int i = 1; i <= r; i++) sumFactor[i] = 1;
    for (int p = 2; p <= r; p++) {
        if (sumFactor[p] != 1) continue;

        vector<int> power(1, 1), sumPower(1, 1);
        while (power.back() * p <= r) {
            power.push_back(power.back() * p);
            sumPower.push_back(sumPower.back() + power.back());
        }

        for (int i = 1; p * i <= r; i++) {
            vp[i] = (i % p ? 0 : vp[i / p] + 1);
            sumFactor[p * i] *= sumPower[vp[i] + 1];
        }
    }

    ll ans = 0;
    for (int i = l; i <= r; i++)
        ans += abs(2 * i - sumFactor[i]);
    cout << ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...