Cod sursa(job #30708)

Utilizator andrei.12Andrei Parvu andrei.12 Data 14 martie 2007 22:03:59
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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[1000], i, j, k, p, n, b;
	long tot[100];
	long  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;
	for (i=11;i<=n;i++){
		for (j=i;j>=2;j--)
			if (ciur[j]==1) if (i%j==0) {
				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);
	return 0;
}