Cod sursa(job #122823)

Utilizator marinMari n marin Data 13 ianuarie 2008 18:48:20
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#define DIM 1000001
int v[DIM];
long int p[DIM];
long long tot[DIM];

long long sum;
long int cnt,e,d,k,n,j,i,a;
long int pas;

int main(){
  FILE *f = fopen("fractii.in","r");
  fscanf(f,"%ld",&n);

  fclose(f);


  for (i=2;i<=n;i++) {
    for (j=2*i;j<=n;j+=i)
      v[j]=1;
  }


  k=0;
  for (i=2;i<=n;i++)
    if (v[i]==0)
      p[++k]=i;

//t(p^e) = (p - 1) * p^(e - 1), p numar prim (din definitie)
//si
//daca p numar prim, p NU divide a,
//t(p^e * a) = t(p^e) * t(a) = (p - 1) * p^(e - 1) * t(a)


  tot[1]=1;
  tot[2]=1;


  for (j=1;(j<=k)&&(p[j]<=n);j++) {
    d=p[j];
    if (d==2)
      pas=d;
    else
      pas=d;
    for (i=d;i<=n;i+=pas)
      if (tot[i]==0){
	a=i;
	e=0;
	while (a%d==0) {
	  e++;
	  a=a/d;
	}
	if (a==1)
	  tot[i]=((long long)(d-1))*(i/d);
	else
	  tot[i]=tot[a]*tot[i/a];

	sum+=(tot[i]+tot[i]);
      }

  }

  if (n==1)
     sum=1;
  else if (n==2) sum=3;
  else sum+=3;

  FILE *g = fopen("fractii.out","w");
  fprintf(g,"%lld",sum);
  fclose(g);
  return 0;
}