oj.uz

Submission #75094

# Submission time Handle Problem Language Result Execution time Memory
75094 2018-09-08T10:02:19 Z charlies_moo Savrsen (COCI17_savrsen) C++17
120 / 120
 2624 ms 39764 KB 
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int p[4000];
    int pc = 0;
    for (int i = 2; i < 4000; i++) {
        bool f = true;
        for (int j = 0; j < pc; j++) {
            if (i % p[j] == 0) {
                f = false;
                break;
            }
        }

        if (f) {
            p[pc++] = i;
        }
    }
    
    int a, b;
    cin >> a >> b;

    int f[b+1];
    f[1] = 1;
    for (int i = 2; i <= b; i++) {
        int q = 0;
        for (int j = 0; j < pc; j++) {
            if (i % p[j] == 0) {
                q = p[j];
                break;
            }
        }
        
        if (q) {
            long long t = q, s = 1;
            while (i % t == 0) {
                s += t;
                t *= q;
            }
            t /= q;
            f[i] = s * f[i/t];
        } else {
            f[i] = i + 1;
        }
    }
    
    long long ans = 0;
    for (int i = a; i <= b; i++) {
        ans += abs(f[i] - i - i);
    }

    cout << ans << endl;

    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 36 ms 948 KB Output is correct
4 Correct 2624 ms 39668 KB Output is correct
5 Correct 2585 ms 39764 KB Output is correct
6 Correct 2596 ms 39764 KB Output is correct
7 Correct 2368 ms 39764 KB Output is correct
8 Correct 676 ms 39764 KB Output is correct