Cod sursa(job #447769)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 30 aprilie 2010 22:40:54
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.34 kb
Raporteaza aceasta sursa 
#include <fstream>
using namespace std;
ifstream in("fractii.in");
ofstream out("fractii.out");
int phi[1000000];
int main ()
{
	long long val = 0;
	int n,i,j;
	in>>n;
	for(i=1;i<=n;i++)
		phi[i] = i-1;
	for(i=2;i<=n;i++)
		for(j=2*i;j<=n;j+=i)
			phi[j]-=phi[i];
	for(i=2;i<=n;i++)
		val+=phi[i];
	out<<(2*val)+1;
	return 0;
}