Cod sursa(job #3273795)

Utilizator anon2718281828Iasmina Matei anon2718281828 Data 3 februarie 2025 21:12:34
Problema Fractii Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("fractii.in");
ofstream out("fractii.out");

int main() {
    int n;
    in >> n;

    vector<int> primes({2});
    vector<bool> nonPrimes(n + 1);

    while (true) {
        int currPrime = primes.back();
        for (long long i = 1LL * currPrime * currPrime; i <= 1LL * n; i++) {
            nonPrimes[i] = nonPrimes[i] || (i % currPrime == 0);
        }

        bool ok = false;
        for (int i = currPrime + 1; i <= n; i++) {
            if (!nonPrimes[i]) {
                ok = true;
                primes.push_back(i);
                break;
            }
        }
        if (!ok) break;
    }

    int sol = 1;
    for (int i = 2; i <= n; i++) {
        if (!nonPrimes[i]) {
            sol += (i - 1) * 2;
        } else {
            int prod = i;
            for (const auto& p: primes) {
                if (i % p == 0) {
                    prod = prod * (p - 1) / p;
                }
            }
            sol += prod * 2;
        }
    }

    out << sol;

    return 0;
}