【二分+高精度快速幂】poj2109

Description

Input

Output

Sample Input

2 16
3 27
7 4357186184021382204544

Sample Output

4
3
1234

题目大意：给出n和p 求出k使k^n=p

看数据范围就知道是要用二分加快速幂，还要高精度……

这个题从12月11号开始做的，但是那一天以后就停竞赛期末复习了，于是没有搞出来的程序一直扔在那儿，今天过生日，奖励自己刷两个题，于是终于过了。

其实一点也不难，不过最开始有好多bug啊！！现在写个高精度各种错，退化啊退化……

还有，二分貌似写得不很科学啊啊啊……

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

long n;
char s[200];
long p[120];
long l[120], r[120], mid[120] ,re[200];
long t[200], y[200];

bool comp1(long *l, long *r)
{
    if (l[0] < r[0]) return 1;
    if (l[0] > r[0]) return 0;
    for (long i=l[0]; i>0; i--)
    {
        if (l[i] < r[i]) return 1;
        if (l[i] > r[i]) return 0;
    }
    return 0;
}

bool comp_deng(long *l, long *r)
{
    if (l[0] != r[0]) return 0;
    for (long i=l[0]; i>0; i--)
    {
        if (l[i] != r[i]) return 0;
    }
    return 1;
}

void sum_div2()
{

    memset(mid, 0, sizeof(mid));
    long len = r[0];
    for (long i=1; i<=len; i++)
    {
        mid[i] += l[i] + r[i];
        mid[i + 1] = mid[i] / 10;
        mid[i] = mid[i] % 10;
    }
    if (mid[len + 1] > 0) len++;


    for (long i=len; i>=1; i--)
    {
        mid[i-1] += mid[i] % 2 * 10;
        mid[i] = mid[i] /2;
    }
    while (mid[len] <= 0) len--;
    mid[0] = len;
}

void cheng(long *a, long *b)
{
    long tmp[400];
    memset(tmp, 0, sizeof(tmp));
    for (long i=1; i<=a[0]; i++)
        for (long j=1; j<=b[0]; j++)
        {
            tmp[i + j -1] += a[i] * b[j];
            tmp[i + j] += tmp[i + j -1] / 10;
            tmp[i + j -1] %= 10;

        }
    long len = a[0] + b[0];
    while (tmp[ len ] == 0) len--;
    if (len >= 200) { len = 200; tmp[200] = 9; }
    tmp[0] = len;


    for (long i=0; i<=tmp[0]; i++)
    {
        a[i] = tmp[i];
    }

}

void power(long n)
{

    memset(t, 0, sizeof(t));
    t[0] = 1;
    t[1] = 1;
    for (long i=0; i<=mid[0]; i++)
    {
        y[i] = mid[i];
    }
    while (n != 0)
    {
        if ((n & 1) == 1)
        {
            cheng(t, y);
        }
        cheng(y, y);
        n = n >> 1;
    }

    for (long i=0; i<=t[0]; i++)
    {
        re[i] = t[i];
    }
}

void add1()
{
    for (long i=0; i<=mid[0]; i++)
    {
        l[i] = mid[i];
    }
    l[1] += 1;
    long i = 1;
    while (l[i] >= 10)
    {
        l[i + 1] += l[i] / 10;
        l[i] = l[i] % 10;
        i++;
    }
    if (l[l[0] + 1] > 0) l[0]++;
}

void plus1()
{
    for (long i=0; i<=mid[0]; i++)
    {
        r[i] = mid[i];
    }
    r[1] -= 1;
    long i = 1;
    while (r[i] < 0)
    {
        r[i + 1] -= 1;
        r[i] += 10;
        i--;
    }
    if (l[l[0]] == 0) l[0]--;
}

void merge(long *a)
{
    while (comp1(l, r))
    {
        sum_div2();
        power(n);
        if (comp_deng(re, p))
        {
            for (long i=0; i<=mid[0]; i++)
            {
                a[i] = mid[i];
            }
            return;
        }
        if (comp1(re, p)) add1();
            else plus1();
    }

    for (long i=0; i<=l[0]; i++)
    {
        a[i] = l[i];
    }
    return;
}

int main()
{
//    freopen("2109.in", "r", stdin);
    while (cin >> n >> s)
    {
        memset(p, 0, sizeof(p));
        memset(r, 0, sizeof(r));
        long len = strlen(s);
        for (long i=0; i<len; i++)
        {
            p[len - i] = s[i] - '0';
            r[len - i] = s[i] - '0';
        }
        p[0] = len;
        r[0] = len;
        memset(l, 0, sizeof(l));
        l[0] = 1; l[1] = 1;

        merge(re);

        for (long i=re[0]; i>0; i--)
        {
            cout<<re[i];
        }
        cout<<endl;
    }
    return 0;
}