Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #define NMax 101
- #define GRUPATE 8
- #define BAZA 100000000
- using namespace std;
- typedef unsigned long long int Huge[NMax];
- FILE *f=fopen("nano.in","r");
- FILE *g=fopen("nano.out","w");
- int n,x;
- Huge y,m,S,D,unu,patrat;
- void Atrib0(Huge H) {
- H[0] = 0;
- }
- void AtribHuge(Huge H, Huge X)
- // H <- X
- {
- int i;
- for (i = 0; i <= X[0]; ++i) {
- H[i] = X[i];
- }
- }
- void Add(Huge A, Huge B)
- /* A <- A+B */
- { int i,T=0;
- if (B[0]>A[0]) // Daca A<B
- { for (i=A[0]+1;i<=B[0];) A[i++]=0; // atunci completez pe A cu zerouri nesemnificative
- A[0]=B[0];
- }
- else for (i=B[0]+1;i<=A[0];) B[i++]=0; // altfel completez pe B cu zerouri nesemnificative
- for (i=1;i<=A[0];i++) // Efectuam adunarea tinand cont de transportllu T
- { A[i]+=B[i]+T;
- T=A[i]/BAZA;
- A[i]%=BAZA;
- }
- if(T) A[++A[0]]=T; // Adaug si llutimllu transport T
- }
- void Subtract(Huge A, Huge B)
- /* A <- A-B */
- { int i, T=0;
- for (i=B[0]+1;i<=A[0];) B[i++]=0;
- for (i=1;i<=A[0];i++)
- A[i]+=(T=(A[i]-=B[i]+T)<0) ? 1 : 0;
- /* Adica A[i]=A[i]-(B[i]+T);
- if (A[i]<0) T=1; else T=0;
- if (T) A[i]+=BAZA; */
- while (!A[A[0]]) A[0]--;
- }
- void MllutHuge(Huge A, Huge B, Huge C)
- /* C <- A x B */
- { int i,j,T=0;
- C[0]=A[0]+B[0]-1;
- for (i=1;i<=A[0]+B[0];) C[i++]=0;
- for (i=1;i<=A[0];i++)
- for (j=1;j<=B[0];j++)
- C[i+j-1]+=A[i]*B[j];
- for (i=1;i<=C[0];i++)
- { T=(C[i]+=T)/BAZA;
- C[i]%=BAZA;
- }
- if (T) C[++C[0]]=T;
- }
- int Divide(Huge A, int X)
- // A <- A/X si intoarce A%X
- {
- int i;
- int R=0;
- for(i=A[0];i;i--)
- {
- A[i]=(R=BAZA*R+A[i])/X;
- R%=X;
- }
- while(A[A[0]]==0&&A[0]>1)
- --A[0];
- return R;
- }
- int Sgn(Huge H1,Huge H2)
- // Elimina zero-urile semnificative, daca exista
- {
- while(H1[0]&&!H1[H1[0]])
- H1[0]--;
- while(H2[0]&&!H2[H2[0]])
- H2[0]--;
- if(H1[0]<H2[0])
- return -1;
- else
- if(H1[0]>H2[0])
- return +1;
- for(int i=H1[0];i>0;--i)
- if (H1[i] < H2[i])
- return -1;
- else
- if(H1[i]>H2[i])
- return +1;
- return 0;
- }
- void afisez(Huge x)
- {
- if(x[0]==0)
- fprintf(g,"%llu",0);
- else
- {
- fprintf(g,"%llu",x[x[0]]);
- for(int i=x[0]-1;i>=1;--i)
- {
- if(x[i]==0)
- fprintf(g,"%s","00000000");
- else
- if(x[i]<10)
- fprintf(g,"%s%llu","0000000",x[i]);
- else
- if(x[i]<100)
- fprintf(g,"%s%llu","000000",x[i]);
- else
- if(x[i]<1000)
- fprintf(g,"%s%llu","00000",x[i]);
- else
- if(x[i]<10000)
- fprintf(g,"%s%llu","0000",x[i]);
- else
- if(x[i]<100000)
- fprintf(g,"%s%llu","000",x[i]);
- else
- if(x[i]<1000000)
- fprintf(g,"%s%llu","00",x[i]);
- else
- if(x[i]<10000000)
- fprintf(g,"%s%llu","0",x[i]);
- else
- fprintf(g,"%llu",x[i]);
- }
- }
- fprintf(g,"%c",'\n');
- }
- int cautare_binara()
- {
- int semn;
- unu[0]=1,unu[1]=1;
- AtribHuge(S,unu);
- AtribHuge(D,y);
- Add(unu,S);
- while(Sgn(S,D)!=1&&Sgn(unu,D)!=0)
- {
- AtribHuge(m,S);
- Add(m,D);
- Divide(m,2);
- MllutHuge(m,m,patrat);
- semn=Sgn(patrat,y);
- if (semn==0) // Verific daca mijlocllu la patrat este egal cu numarllu
- return 1;
- if (semn==1) // patrat<y => caut la stanga
- AtribHuge(D,m);
- if(semn==-1) // patrat>y => caut la dreapta
- AtribHuge(S,m);
- unu[0]=1,unu[1]=1;
- Add(unu,S);
- }
- return 0;
- }
- int main()
- {
- fscanf(f,"%d",&n);
- int rest,cat,nr;
- for(int i=1;i<=n;++i)
- {
- fscanf(f,"%d\n",&x);
- char s[x+1];
- int indice=0;
- fscanf(f,"%s",s);
- rest=x%GRUPATE,cat=x/GRUPATE;
- if(rest)
- {
- y[0]=cat+1;
- nr=0;
- for(int k=1;k<=rest;++k)
- nr=nr*10+s[indice++]-'0';
- y[y[0]]=nr;
- for(int j=y[0]-1;j>=1;--j)
- {
- nr=0;
- for(int k=1;k<=GRUPATE;++k)
- nr=nr*10+s[indice++]-'0';
- y[j]=nr;
- }
- }
- else
- {
- y[0]=cat;
- for(int j=y[0];j>=1;--j)
- {
- nr=0;
- for(int k=1;k<=GRUPATE;++k)
- nr=nr*10+s[indice++]-'0';
- y[j]=nr;
- }
- }
- if(cautare_binara())
- afisez(y);
- }
- fclose(f);
- fclose(g);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement