oj.uz

Submission #1109415

# Submission time Handle Problem Language Result Execution time Memory
1109415 2024-11-06T16:11:11 Z _callmelucian Savrsen (COCI17_savrsen) C++14
120 / 120
 195 ms 62544 KB 
#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 (ll p = 2; p <= r; p++) {
        if (sumFactor[p] != 1) continue;

        vector<ll> 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 (ll 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;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 173 ms 62280 KB Output is correct
5 Correct 186 ms 62544 KB Output is correct
6 Correct 195 ms 62280 KB Output is correct
7 Correct 172 ms 57928 KB Output is correct
8 Correct 36 ms 19024 KB Output is correct