Cod sursa(job #13627)

Utilizator anamaria1Ozorchevici Ana Maria anamaria1 Data 7 februarie 2007 11:44:32
Problema Fractii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#pragma option -3 -r -Z -O2 -a
#include<fstream.h>
#include<math.h>
#define dim 999999
long (*v)=new long[dim];
//int w[13],cif[7];
long cmmdc(long a,long b)
{long r;
do
 {r=a%b;a=b;b=r;}
while(r);
return a;
}
int prim(long x,long &d1,long &d2,long &b)
{long jum,r,i;
int ok=0;
jum=(long)sqrt(x);
if((x%2)==0)
  {for(i=2;i<=jum;i++)
    if((x%i)==0)
     {d1=i;d2=x/i;r=cmmdc(d1,d2);
      if(r==1) return 2;
       else if(!ok) {ok=1;b=d1;}
     }
   return 3;    
  }
 else
  {for(i=3;i<=jum;i++)  
    if((x%i)==0)
     {d1=i;d2=x/i;r=cmmdc(d1,d2);
      if(r==1) return 2;
       else if(!ok) {ok=1;b=d1;}
     }
   if(ok) return 3;
    else return 1;
  }
}
/*void trnr(long val,int &l)
{int i;
for(i=0;i<7;i++) cif[i]=0;
while(val)
 {cif[l]=val%10;val=val/10;l++;}
}
void adun(int l,int &l2)
{int t=0,i;
for(i=0;i<l;i++)
 {w[i]=w[i]+cif[i]+t;t=w[i]/10;w[i]=w[i]%10;}
while(t)
 {w[i]=w[i]+t;t=w[i]/10;w[i]=w[i]%10;i++;}
i--;
if(i>l2) l2=i; 
} */
int main()
{ifstream f("fractii.in");
ofstream g("fractii.out");
long i,d1,d2,b,n;
unsigned long s;
int ok;//,l,l2;
f>>n;f.close();
if(n==1) {g<<1<<'\n';g.close();return 0;}
if(n==2) {g<<3<<'\n';g.close();return 0;}
//if(n==1000000) {g<<"607927104783"<<'\n';g.close();return 0;}
v[0]=1;v[1]=2;n=n-2;
for(i=2;i<=n;i++)
 {d1=d2=b=0;
  ok=prim(i+2,d1,d2,b);
  if(ok==1) v[i]=i+1;
   else if(ok==2) v[i]=v[d1-2]*v[d2-2];
	  else
	   {d1=(i+2)/b;v[i]=i+2-d1;}
 }
s=1;
//w[0]=1;l2=0;
for(i=0;i<=n;i++)
 {v[i]=v[i]*2;//l=0;trnr(v[i],l);adun(l,l2);}
  s=s+v[i];
 }
//for(i=l2;i>=0;i--) g<<w[i];
g<<s<<'\n';g.close();
return 0;
}