Cod sursa(job #2749886)

Utilizator capra123capra leonardo capra123 Data 8 mai 2021 21:28:18
Problema Fractii Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("fractii.in");
ofstream fout("fractii.out");

int n;

const int nmax = 1e6 + 1;
bitset<nmax> prime;
vector<int> fact[nmax];
int main()
{
    fin >> n;

    int i , j;

    for(i=4;i<=n;i+=2 )
        {prime[i] = 1;
        fact[i].push_back(2);
        }
    fact[2].push_back(2);


    for(i=3;i<=n;i+=2)
        if(prime[i] == 0)
    {   fact[i].push_back(i);
        for(j=2*i;j<=n;j+=i)
            {prime[j] = 1;
             fact[j].push_back(i);
            }
    }
    long long result = 0 , maxi = 1 , value = 1;

    for(i=2;i<=n;++i)
    {   int res = i;
        for(auto nr: fact[i])
        {
            res/=nr;
            res *= (nr - 1);
        }

        result += 1LL*2*res;

    }

    fout << result + 1;
    return 0;
}