Cod sursa(job #48020)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 aprilie 2007 12:43:31
Problema Fractii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#define max 100000
int i, p, s, nr, ciur[max], vpr[100000];
long long suma;
void div(){
	int j;
	for (j=0;j<nr;j++)
		if (i%vpr[j]==0) { p=vpr[j]; if ((i/p)%p==0) s=1; else s=0; break;}
}
int main(){
	freopen("fractii.in","r",stdin);
	freopen("fractii.out","w",stdout);
	int j, tot[max], n;
	scanf("%d",&n);
	for (i=2;i*i<=max;i++)
		if (ciur[i]==0){
			j=i+i;
			while (j<=max){
				ciur[j]=1;
				j+=i;
			}
		}
	nr=0;
	for (i=2;i<=max;i++)
		if (ciur[i]==0) { vpr[nr]=i; nr++;}
	tot[1]=1;
	tot[2]=1;
	tot[3]=2;
	tot[4]=2;
	tot[5]=4;
	tot[6]=2;
	tot[7]=6;
	tot[8]=4;
	tot[9]=6;
	tot[10]=4;
	for (i=11;i<=n;i++){
		div();
		if (s==1) tot[i]=p*tot[i/p];
		else tot[i]=(p-1)*tot[i/p];
	}
	suma=0;
	for (i=2;i<=n;i++)
		suma+=tot[i];
	printf("%lld",2*suma+1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}