inequation_caut_bin

#include <fstream>
#include <cstring>
#define Nmax 10001
using namespace std;
typedef int Huge[Nmax];
int n,b;
Huge N,NN,y,unu;

void Nr_Huge(Huge X,int n) /// X <- n
{
    int i=0;
    X[0]=0;
    if(n==0)
        X[0]=1,X[1]=0;
    else
        while(n)
            ++X[0],X[++i]=n%10,n/=10;
}

void Add(Huge A,Huge B) /// A <- A+B
{
    int i,T=0;
    if(B[0]>A[0])
    {
        for(i=A[0]+1;i<=B[0];)
            A[i++]=0;
        A[0]=B[0];
    }
    else
        for(i=B[0]+1;i<=A[0];)
            B[i++]=0;
    for(i=1;i<=A[0];i++)
        A[i]+=B[i]+T,T=A[i]/10,A[i]%=10;
    if(T)
        A[++A[0]]=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)?10:0; /// Adica A[i]=A[i]-(B[i]+T); if (A[i]<0) T=1; else T=0; if (T) A[i]+=10; */
    while (!A[A[0]])
        --A[0];
}

void Mult(Huge H,int X) /// H <- H*X
{
    int T=0;
    for(int i=1;i<=H[0];++i)
        H[i]=H[i]*X+T,T=H[i]/10,H[i]=H[i]%10;
    while(T) /// Cat timp exista transport
        H[++H[0]]=T%10,T/=10;
}

void MultHuge(Huge A,Huge B) /// A <- A x B
{
    if(B[0]==1&&B[1]==0) /// Verific daca al doilea numar este 0
    {
        A[0]=1;
        A[1]=0;
        return;
    }
    int i,j,T=0;
    Huge C;
    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)/10,C[i]%=10;
    if(T)
        C[++C[0]]=T;
    for(i=0;i<=C[0];++i)
        A[i]=C[i];
}

int Sgn(Huge H1,Huge H2) /// -1 daca H1<H2; 0 daca H1=H2 si 1 daca H1>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 putere(Huge B,int n)
{
    Nr_Huge(B,b);--n; /// B <- b^1
    while(n)
    {
        if(n%2==0)
            MultHuge(N,N),n/=2;
        else
            MultHuge(B,N),--n;
    }
}

int cautbin(int st,int dr)
{
    int mij=(st+dr)/2;
    if(st>dr)
        return st-1;
    Huge BlaN;
    Nr_Huge(N,b);
    putere(BlaN,mij);
    int semn=Sgn(BlaN,y);
    if(semn==1)
        cautbin(st,mij-1);
    if(semn==-1)
        cautbin(mij+1,dr);
    if(semn==0)
        return mij;
}

int main()
{
    ifstream f("inequation.in");
    ofstream g("inequation.out");
    int t;
    f>>t;
    char s[25001];
    while(t--)
    {
        f>>b;
        f>>n;
        f.get();
        f.get(s,25001);
        for(int i=1;i<=n;++i)
            y[n-i+1]=s[i-1]-'0';
        y[0]=n;
        unu[0]=1;unu[1]=1; /// unu <- 1
        Mult(y,b-1); Add(y,unu);
        g<<cautbin(1,n*n)<<'\n';
    }
    f.close();
    g.close();
    return 0;
}