Cod sursa(job #30372)

Utilizator andrei.12Andrei Parvu andrei.12 Data 13 martie 2007 20:35:29
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
using namespace std;
#include<stdio.h>
int main(){
	FILE*f=fopen("fractii.in", "r");
	FILE*g=fopen("fractii.out", "w");
	long n, i, j, pr, k, r, t, w[1000], nr, prime[50], s;
	int ciur[1000000];
	long long suma;
	fscanf(f,"%lld", &t);
	n=t;
	suma=0;
	for (j=2;j<=n;j++)
		ciur[j]=1;
	for (j=2;j*j<=n;j++)
		if (ciur[j]==1){
			k=2;
			while (j*k<=n){
				ciur[j*k]=0;
				k++;
			}
		}
	nr=0;
	for (i=2;i<=n;i++){
		if (ciur[i]==1) { w[nr]=i; nr++;}
	}
	for (i=2;i<=n;i++){
		t=0;
		s=0;
		for (j=0;j<nr&&s==0;j++)
			if (w[j]<=i) {if (i%w[j]==0){ prime[t]=w[j]; t++;}}
			else s=1;
		pr=1;
		r=i;
		for (j=0;j<t;j++){
			r=r/prime[j];
			pr=pr*(prime[j]-1);
		}
		suma=suma+pr*r;
	}
	fprintf(g,"%lld\n", 2*suma+1);
	fclose(f);
	fclose(g);
	return 0;
}