Cod sursa(job #281471)

Utilizator zoltrixOLARU SABIN zoltrix Data 14 martie 2009 23:05:46
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 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);
 return 0;
 }