Cod sursa(job #644689)

Utilizator giuliastefGiulia Stef giuliastef Data 7 decembrie 2011 14:26:42
Problema Fractii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
// infoarena 1.0 - fractii

#include <fstream>
using namespace std;
char sir[1000001];
int t[1000001];

int main()
{
    long int n,i,j,q;
    long long c=1;
    ifstream f("fractii.in");
    ofstream g("fractii.out");
    f>>n;
    t[1]=1;
    for(i=2;i<=n;i++)  
    {  
      if(sir[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)  
        {  
              sir[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];                   
        }         
      }  
      c+=2*t[i];  
    }  
    g<<c<<"\n";
    f.close();
    g.close();
    return 0;
}