Cod sursa(job #281472)

Utilizator zoltrixOLARU SABIN zoltrix Data 14 martie 2009 23:10:24
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
   #include <stdio.h>

   long  s[1000001];
   int  t[1000001];

 void main ()
   {
     long long nrf;
     int i ,j, q, n;

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

     for(i=2;i<=n;i++)
     {
       if(s[i]==0)
       {
	 t[i]=i-1;
	 if(i<=n/i+1)
	   for(j=i*i; j<=n; j*=i)
	       t[j]=t[j/i]*i;

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