Cod sursa(job #30791)

Utilizator andrei.12Andrei Parvu andrei.12 Data 15 martie 2007 08:57:40
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<math.h>
long long wop(long a, long b){
	long long i, p=1;
	for (i=1;i<=b;i++)
		p*=a;
	return p;
}
int main(){
	FILE*f=fopen("fractii.in","r");
	FILE*g=fopen("fractii.out","w");
	int ciur[500000], i, j, k, p, n, b, s;
	long long tot[500000], suma;
	float a;
	fscanf(f,"%ld",&n);
	for (i=2;i<=n;i++)
		ciur[i]=1;
	for (i=2;i*i<=n;i++)
		if (ciur[i]==1){
			j=2;
			while (i*j<=n){
				ciur[i*j]=0;
				j++;
			}
		}
	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;
	tot[11]=10;
	tot[12]=4;
	tot[13]=12;
	tot[14]=6;
	tot[15]=8;
	tot[16]=8;
	tot[17]=16;
	tot[18]=6;
	tot[19]=18;
	tot[20]=8;
	for (i=21;i<=n;i++){
		s=0;
		for (j=i;j>=2&&s==0;j--)
			if (ciur[j]==1) if (i%j==0) {
				s=1;
				k=j;
				a=i/j;
				p=0;
				while (floor(a)==a){
					p++;
					a=a/j;
				}
			}
		b=i/pow(k,p);
		tot[i]=(k-1)*wop(k,p-1)*tot[b];
	}
	suma=0;
	for (i=2;i<=n;i++)
		suma+=tot[i];
	fprintf(g,"%lld",2*suma+1);
	fclose(f);
	fclose(g);
	return 0;
}