Mai intai trebuie sa te autentifici.
Cod sursa(job #80227)
Utilizator | Florin Ghesu floringh06 | Data | 26 august 2007 23:04:38 |
---|---|---|---|
Problema | Fractii | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.11 kb |
using namespace std;
#include<stdio.h>
FILE *fin=fopen("fractii.in","r"),
*fout=fopen("fractii.out","w");
int p[1000220];
long long sol[1000220];
int n;
long long rez;
void generate()
{
int i,j,k;
p[1]=0;
p[2]=0;
for (i=2; i<=n/2+1; i++)
{
k=i*i;
while (k<=n)
{
p[k]=1;
k+=i;
}
}
}
void solve()
{
int i,k;
for (i=1; i<=n; i++)
sol[i]=i;
for (i=2; i<=n/2; i++)
if (p[i]==0)
{
sol[i]=(long long)sol[i]*(i-1)/i;
k=i+i;
while (k<=n)
{
sol[k]=(long long)sol[k]*(i-1)/i;
k+=i;
}
}
for (i=n/2+1; i<=n; i++)
if (p[i]==0) sol[i]=(long long)sol[i]*(i-1)/i;
rez=0;
// fprintf(fout,"%d\n",sol[i]);
}
int main()
{
int i;
fscanf(fin,"%d",&n);
generate();
solve();
for (i=1; i<=n; i++) rez+=(long long)sol[i]; rez=(long long)2*rez-1;
fprintf(fout,"%lld\n",rez);
fclose(fin);
fclose(fout);
return 0;
}