Cod sursa(job #3173877)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 23 noiembrie 2023 20:47:07
Problema Fractii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

void solve() {
  int n;
  cin >> n;

  vector<int> lp(1 + n, 0);
  lp[0] = lp[1] = 1;
  for (int i = 2; i * i <= n; ++i) {
    if (lp[i] != 0)
      continue;

    for (int j = i * i; j <= n; j += i)
      if (lp[j] == 0)
        lp[j] = i;
  }

  for (int i = 2; i <= n; ++i)
    if (lp[i] == 0)
      lp[i] = i;

  long long count = 1;
  set<int> divisors;
  for (int i = 2, nr; i <= n; ++i) {
    nr = i;
    while (nr != 1) {
      divisors.insert(lp[nr]);
      nr /= lp[nr];
    }

    int total = i;
    for (int d : divisors)
      total = (total / d) * (d - 1);

    count += 2 * total;

    divisors.clear();
  }

  cout << count << endl;
}

int main() {
  freopen("fractii.in", "r", stdin);
  freopen("fractii.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}