Cod sursa(job #477211)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 13 august 2010 20:12:23
Problema Fractii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>

using namespace std;
bool prim[1000000];
int s[100001],x,ind,nr,suma,k;
int lgput(int a,int p)
{
 int i,sol=1;

	for (i = 0; (1<<i) <= p; ++ i)
	{
		if ( ((1<<i) & p) > 0)
 			sol*=a;
      a*= a;
	}
	return sol;
}

int main()
{
    int i,j,n;
    ifstream fi("fractii.in");
    ofstream fo("fractii.out");
    fi>>n;
    for(i=2;i<=1000000;i++)
    if(!prim[i])
    {
      for(j=i+i;j<=1000000;j+=i)
        prim[j]=1;
      s[++k]=i;
    }
    suma=0;
    for(i=2;i<=n;i++)
    {
      x=i;
      ind=1;
      for(j=1;j<=k and s[j]<=x;j++)
      if(!(x%s[j]))
      {
        nr=0;
        while(!(x%s[j])) { nr++; x/=s[j]; }

        ind*=(s[j]-1)*lgput(s[j],nr-1);
      }
      suma+=ind;
    }
    fo<<suma*2+1<<"\n";
    return 0;
}