oj.uz

Submission #1109417

# Submission time Handle Problem Language Result Execution time Memory
1109417 2024-11-06T16:12:04 Z _callmelucian Savrsen (COCI17_savrsen) C++14
120 / 120
 212 ms 62312 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 (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;
}

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 189 ms 62308 KB Output is correct
5 Correct 209 ms 62312 KB Output is correct
6 Correct 212 ms 62312 KB Output is correct
7 Correct 191 ms 57936 KB Output is correct
8 Correct 42 ms 19024 KB Output is correct