Cod sursa(job #2740306)
Utilizator | Lupau Claudiu ClaudiuAL | Data | 12 aprilie 2021 15:14:19 |
---|---|---|---|
Problema | Fractii | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.57 kb |
#include <bits/stdc++.h>
using namespace std;
vector<int> ph;
void fracti(int n)
{
for(int i=0; i<=n; i++)
ph[i]=i;
for(int i=2; i<=n; i++)
{
if(ph[i]==i)
{
for(int j=i; j<=n; j+=i)
ph[j]=ph[j]-ph[j]/i;
}
}
}
int main()
{
ifstream fin("fractii.in");
ofstream fout("fractii.out");
int n;
fin>>n;
ph = vector<int>(n+1);
fracti(n);
long long count=1;
for(int i=2; i<=n; i++)
{
count=count+2*ph[i];
}
fout<< count;
}