oj.uz

답안 #1109413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109413 2024-11-06T16:09:57 Z _callmelucian Savrsen (COCI17_savrsen) C++14
120 / 120
 206 ms 117848 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;
ll 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 200 ms 117832 KB Output is correct
5 Correct 201 ms 117840 KB Output is correct
6 Correct 206 ms 117848 KB Output is correct
7 Correct 202 ms 111412 KB Output is correct
8 Correct 38 ms 31312 KB Output is correct