Rezolvare

Iată rezolvarea de 100 de puncte pentru problema hn:

// sursa 100 puncte cu observatii recurente

#include<fstream>
#include<iomanip>
#include <cassert>

#define baza_1 1073741823
#define baza2 1000000000
using namespace std;

ifstream  fin("hn.in");
ofstream fout("hn.out");

int n,np,p[1500]; char ciur[10002];
struct mare{
    int v[490],nv;///cifrele sunt asezate invers, v[0] este cifra unitatilor
};

void suma_mare_mare(mare &a, mare &b){
    long long t=0; int i,nc;
    i=a.nv; while(i<b.nv)a.v[i++]=0;
    i=b.nv;while(i<a.nv)b.v[i++]=0;
    nc=max(a.nv,b.nv);
    for(i=0;i<=nc-1;i++){  t=t+a.v[i]+b.v[i];  a.v[i]=t&baza_1;  t=(t>>30);  }
    while(t){ a.v[nc]=t&baza_1; t=(t>>30); nc++; }
    a.nv=nc;
}
void suma_mare_mic(mare &a, int b){
    long long t; int i,nc;
    nc=a.nv;
    t=a.v[0];t+=b;
    a.v[0]=t%baza2; t=t/baza2;
    for(i=1;t && i<=nc-1;i++){  t=t+a.v[i];  a.v[i]=t%baza2;  t=t/baza2;  }
    while(t){ a.v[nc]=t%baza2; t=t/baza2; nc++; }
    a.nv=nc;
}
void produs_mare_mic(mare &a, int b){
    long long t=0;
    for(int i=0;i<=a.nv-1;i++){
        t=t+(long long)a.v[i]*b;
        a.v[i]=t&baza_1;
        t=(t>>30);
    }
    while(t){
        a.v[a.nv]=t&baza_1;
        t=(t>>30);
        a.nv++;
    }
}
void produs_mare_mic2(mare &a, int b){
    long long t=0;
    for(int i=0;i<=a.nv-1;i++){ t=t+(long long)a.v[i]*b;  a.v[i]=t%baza2; t=t/baza2; }
    while(t){  a.v[a.nv]=t%baza2;  t=t/baza2;   a.nv++; }
}
void div_mare_mic(mare &a, int b, mare &c, int &r){
    long long rr=0;
    for(int k=a.nv-1;k>=0;k--){
        rr=(rr<<30)+a.v[k];  c.v[k]=rr/b; rr=rr%b;
    }
    c.nv=a.nv; while(c.nv>1 && c.v[c.nv-1]==0){ c.nv--;}
    r=rr;
}
void fafis(mare &x){
  mare z;
  z.nv=1;z.v[0]=x.v[x.nv-1];
  for(int i=x.nv-2;i>=0;i--){
    produs_mare_mic2(z,(1<<30));
    suma_mare_mic(z,x.v[i]);
  }
  fout<<z.v[z.nv-1];
  for(int i=z.nv-2;i>=0;i--){
      fout<<setfill('0')<<setw(9)<<z.v[i];
  }
  fout<<"\n";
}
int main(){
    int i,j,k,q,r,c,q1;
    fin>>n;
    //assert(n>=2 && n<=36);
    //assert(n>=37 && n<=1512);
    //assert(n>=1513 && n<=4003);
    //assert(n>=4004 && n<=10000);
    mare numa, numi, x, y;
    np=0;
    for(i=2;i<=n;i++){
      if(ciur[i]==0){
        p[++np]=i;
        for(j=i*i;j<=n;j=j+i)ciur[j]=1;
      }
    }
    numi.nv=1;numi.v[0]=1;
    c=0;q1=1;
    for(i=1;i<=np;i++){
      k=p[i];q=k;while(q*k<=n){q*=k;}
      c++;q1*=q;
      if(c==2){
        produs_mare_mic(numi,q1);
        c=0;q1=1;
      }
    }
    if(c!=0)produs_mare_mic(numi,q1);

    numa.nv=1;numa.v[0]=0;
    for(c=1,j=n;j;j=k){
      x.nv=1;x.v[0]=0;k=j/2;
      for(i=j+j%2-1;i>k;i=i-2){
          div_mare_mic(numi,i,y,r);
          suma_mare_mare(x,y);
      }
      div_mare_mic(x,c,y,r);
      c=c*2;
      produs_mare_mic(y,c-1);
      suma_mare_mare(numa,y);
    }
    for(i=2;i<=np;i++){q=p[i];
        do{
          div_mare_mic(numa,q,x,j);
          if(j==0)div_mare_mic(numi,q,y,k);
          else break;
          if(k==0){numa=x; numi=y;}
          else break;
        }while(1);
    }
    fafis(numa); fafis(numi);
    fout.close();fin.close(); return 0;
}