Cod sursa(job #280732)

Utilizator space.foldingAdrian Soucup space.folding Data 13 martie 2009 15:41:26
Problema Fractii Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#define MAX_UL 0xffffffff
bool sir[1000001];
int t[1000001];

int main ()
{
  unsigned long long nrfractii;
  unsigned int i ,j, q, n;

  freopen("fractii.in", "r", stdin);
  freopen("fractii.out", "w", stdout);
  scanf("%d", &n);
  
  nrfractii=1;
  t[1]=1;

  for(i=2;i<=n;i++)
  {
    if(sir[i]==0)
    {
      t[i]=i-1;
	  for(j=i*i; j<=n && j<MAX_UL/i; j*=i)
	  {
		t[j]=t[j/i]*i;
	  }
	  for(j=i*2; j<=n; j+=i)
	  {
		  	sir[j]=1;
			for(q=i; q<MAX_UL/i && q<=n && j%q==0; q*=i)
				if(!t[j] && (j/i)%q!=0)
					t[j]=t[q]*t[j/q];		
	  }	  	  
    }
    nrfractii+=2*t[i];
  }
  printf("%lld", nrfractii);
  return 0;
}