Cod sursa(job #3154576)
| Utilizator | Data | 5 octombrie 2023 11:04:28 | |
|---|---|---|---|
| Problema | Fractii | Scor | 30 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 1.07 kb |
#include <iostream>
#include <fstream>
using namespace std;
//int cmmdc(int a, int b)
//{
// while(a!=b)
//{
// if(a>b)
//{
// a=a-b;
// }
// else
// {
// b=b-a;
// }
//}
// return a;
//}
int euclid(int N)
{
int phi,d;
phi=N;
for(d=2;d<=N*N;d++)
{
if(N%d==0)
{
phi=phi/d*(d-1);
while(N%d==0)
{
N=N/d;
}
}
}
if(N>1)
{
phi=phi/N*(N-1);
}
return phi;
}
int main()
{
ifstream f("fractii.in");
ofstream g("fractii.out");
int N,i,t=0;
f>>N;
for(i=1;i<=N;i++)
{
//for(j=1;j<=N;j++)
//{
//if(cmmdc(i,j)==1)
//{
//t++;
//}
//}
if(i>1)
{
t=t+euclid(i)*2;
}
else
{
t=t+euclid(i);
}
}
g<<t;
f.close();
g.close();
return 0;
}
