Pagini recente » Cod sursa (job #2228129) | Cod sursa (job #2415437) | Cod sursa (job #553595) | Cod sursa (job #1003433) | Cod sursa (job #30791)
Cod sursa(job #30791)
#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;
}