40 pts 求调
查看原帖
40 pts 求调
757432
laijingnian楼主2023/11/11 15:48
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;

#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in freopen("in.txt","r",stdin);
#define out freopen("out.txt","w",stdout);
#define endl "\n"

typedef long long ll;
const ll MOD = 998244353;//1e9+7
const ll N = 2e5+10;
const ll MAXBIT = 60;
const ll INF = 1e18;
const double eps = 1e-8;

struct Bignum 
{
    int num[N];
    bool compare (const Bignum a, const Bignum b) 
	{
        int len1 = a.num[0], len2 = b.num[0], flag;
        if (len1 > 0 && len2 > 0) flag = 1;
        else if (len1 < 0 && len2 < 0) flag = 2;
        else 
		{
            if (len1 > 0 && len2 < 0) return true;
            else return false;
        }
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        if (flag == 1) 
		{
            if (len1 > len2) return true;
            else if (len1 < len2) return false;
            else 
			{
                for (int i = len1; i >= 1; i --) 
				{
                    if (a.num[i] > b.num[i]) return true;
                    else if (a.num[i] < b.num[i]) return false;
                }
                return true;
            }
        } 
		else 
		{
            if (len1 > len2) return false;
            else if (len1 < len2) return true;
            else 
			{
                for (int i = len1; i >= 1; i --) 
				{
                    if (a.num[i] > b.num[i]) return false;
                    else if (a.num[i] < b.num[i]) return true;
                }
                return true;
            }
        }
    }
    Bignum change (long long a) 
	{
        Bignum ans;
        memset(ans.num, 0, sizeof(ans.num));
        long long x = a < 0 ? - a : a;
        while (x) 
		{
            ans.num[++ ans.num[0]] = x % 10;
            x /= 10;
        }
        if (a < 0) ans.num[0] = - ans.num[0];
        if (!a)
            ans.num[0] = 1;
        return ans;
    }
    bool operator > (const Bignum &a) 
	{
        if (!compare(a, *this)) return true;
        else return false;
    }
    bool operator < (const Bignum &a) 
	{
        if (!compare(*this, a)) return true;
        else return false;
    }
    bool operator >= (const Bignum &a) 
	{
        if (compare(*this, a)) return true;
        else return false;
    }
    bool operator <= (const Bignum &a) 
	{
        if (compare(a, *this)) return true;
        else return false;
    }
    bool operator == (const Bignum &a) 
	{
        if (compare(*this, a) && compare(a, *this)) return true;
        else return false;
    }
    bool operator != (const Bignum &a) 
	{
        if (compare(*this, a) && compare(a, *this)) return false;
        else return true;
    }
    Bignum add (const Bignum &a, const Bignum &b) 
	{
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = max(len1, len2) + 1;
        int x = 0;
        for (int i = 1; i <= len; i ++) 
		{
            ans.num[i] = a.num[i] + b.num[i] + x;
            x = ans.num[i] / 10;
            ans.num[i] %= 10;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum minus (const Bignum &a, const Bignum &b) 
	{
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = max(len1, len2);
        int x = 0;
        for (int i = 1; i <= len; i ++) 
		{
            ans.num[i] = a.num[i] - b.num[i] + x;
            if (ans.num[i] < 0) 
			{
                ans.num[i] += 10;
                x = -1;
            } 
			else
                x = 0;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum multiply (const Bignum &a, const Bignum &b) 
	{
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = len1 + len2;
        for (int i = 1; i <= len1; i ++) 
		{
            int x = 0;
            for (int j = 1; j <= len2; j ++) 
			{
                ans.num[i + j - 1] += a.num[i] * b.num[j] + x;
                x = ans.num[i + j - 1] / 10;
                ans.num[i + j - 1] %= 10;
            }
            ans.num[len2 + i] += x;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum divide (const Bignum &a, const Bignum &b, int flag) 
	{
        Bignum ans = change(0), tmp1, tmp2;
        tmp1 = a;
        tmp2 = b;
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = len1 - len2 + 1;
        tmp1.num[0] = len1;
        tmp2.num[0] = len2;
        for (int i = 1; i < len; i ++) tmp2 = multiply(tmp2, change(10));
        for (int i = len; i >= 1; i --) 
		{
            while (tmp1 >= tmp2) 
			{
                tmp1 = minus(tmp1, tmp2);
                ans.num[i] ++;
            }
            for (int j = 1; j < tmp2.num[0]; j ++)
                tmp2.num[j] = tmp2.num[j + 1];
            tmp2.num[tmp2.num[0] --] = 0;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        if (flag == 1) return ans;
        else return tmp1;
    }
    Bignum operator + (const Bignum &a) 
	{
        Bignum tmp, tmp1, tmp2;
        if (num[0] > 0 && a.num[0] > 0)
            tmp = add(*this, a);
        else if (num[0] < 0 && a.num[0] < 0) 
		{
            tmp = add(*this, a);
            tmp.num[0] = - tmp.num[0];
        } 
		else 
		{
            tmp1 = *this, tmp2 = a;
            if (num[0] < 0) 
			{
                tmp1.num[0] = - tmp1.num[0];
                if (tmp1 > tmp2) 
				{
                    tmp = minus(tmp1, tmp2);
                    tmp.num[0] = - tmp.num[0];
                } 
				else
                    tmp = minus(tmp2, tmp1);
            } 
			else 
			{
                tmp2.num[0] = - tmp2.num[0];
                if (tmp1 > tmp2)
                    tmp = minus(tmp1, tmp2);
                else 
				{
                    tmp = minus(tmp2, tmp1);
                    tmp.num[0] = - tmp.num[0];
                }
            }
        }
        return tmp;
    }
    Bignum operator - (const Bignum &a) 
	{
        Bignum tmp;
        if (num[0] > 0 && a.num[0] > 0) 
		{
            if (*this >= a)
                tmp = minus(*this, a);
            else 
			{
                tmp = minus(a, *this);
                tmp.num[0] = - tmp.num[0];
            }
        } 
		else if (num[0] < 0 && a.num[0] < 0) 
		{
            if (*this >= a)
                tmp = minus(a, *this);
            else 
			{
                tmp = minus(*this, a);
                tmp.num[0] = - tmp.num[0];
            }
        } 
		else 
		{
            if (num[0] < 0) 
			{
                tmp = add(*this, a);
                tmp.num[0] = - tmp.num[0];
            } 
			else
                tmp = add(*this, a);
        }
        return tmp;
    }
    Bignum operator * (const Bignum &a) 
	{
        Bignum tmp;
        if (num[0] > 0 && a.num[0] > 0)
            tmp = multiply(*this, a);
        else if (num[0] < 0 && a.num[0] < 0)
            tmp = multiply(*this, a);
        else 
		{
            tmp = multiply(*this, a);
            tmp.num[0] = - tmp.num[0];
        }
        return tmp;
    }
    Bignum operator / (const Bignum &a) 
	{
        Bignum tmp, tmp1, tmp2;
        tmp1 = *this;
        tmp2 = a;
        if (num[0] < 0) tmp1.num[0] = - tmp1.num[0];
        if (a.num[0] < 0) tmp2.num[0] = - tmp2.num[0];
        if (tmp1 < tmp2)
            tmp = change(0);
        else 
		{
            if (num[0] > 0 && a.num[0] > 0)
                tmp = divide(*this, a, 1);
            else if (num[0] < 0 && a.num[0] < 0)
                tmp = divide(*this, a, 1);
            else 
			{
                tmp = divide(*this, a, 1);
                tmp.num[0] = - tmp.num[0];
            }
        }
        return tmp;
    }
    Bignum operator % (const Bignum &a) 
	{
        Bignum tmp, tmp1, tmp2;
        tmp1 = *this;
        tmp2 = a;
        if (num[0] < 0) tmp1.num[0] = - tmp1.num[0];
        if (a.num[0] < 0) tmp2.num[0] = - tmp2.num[0];
        if (tmp1 < tmp2)
            tmp = tmp1;
        else 
		{
            tmp = divide(tmp1, tmp2, 2);
            if (tmp != change(0) && num[0] < 0) tmp.num[0] = - tmp.num[0];
        }
        return tmp;
    }
    Bignum Power (const Bignum &a) 
	{
        Bignum res = change(1), tmp1 = *this, tmp2 = a;
        while (tmp2 != change(0)) 
		{
            if (tmp2.num[1] % 2 == 1) res = res * tmp1;
            tmp1 = tmp1 * tmp1;
            tmp2 = tmp2 / change(2);
        }
        return res;
    }
    Bignum Sqrt (const Bignum &a) 
	{
        Bignum l = change(1), r = *this, mid;
        while (l <= r) 
		{
            mid = (l + r) / change(2);
            if (mid.Power(a) <= *this)
                l = mid + change(1);
            else
                r = mid - change(1);
        }
        return r;
    }
    void read () 
	{
        memset(num, 0, sizeof(num));
        char ch = getchar();
        int flag = 1, len = 0;
        Bignum tmp;
        while (ch < '0' || ch > '9') 
		{
            if (ch == '-') flag = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') 
		{
            tmp.num[++ len] = ch - '0';
            ch = getchar();
        }
        for (int i = 1; i <= len; i ++)
            num[i] = tmp.num[len - i + 1];
        if (flag == -1) len = - len;
        num[0] = len;
    }
    void write () 
	{
        int len;
        if (num[0] < 0) 
		{
            putchar('-');
            len = - num[0];
        } 
		else
            len = num[0];
        for (int i = len; i >= 1; i --)
            putchar(num[i] + 48);
        printf("\n");
    }
};
Bignum change (long long a) 
{
    Bignum ans;
    memset(ans.num, 0, sizeof(ans.num));
    long long x = a < 0 ? - a : a;
    while (x) 
	{
        ans.num[++ ans.num[0]] = x % 10;
        x /= 10;
    }
    if (a < 0) ans.num[0] = - ans.num[0];
    if (!a)
        ans.num[0] = 1;
    return ans;
}

Bignum quick_power(Bignum a, Bignum k)
{
    Bignum res = change(1);
    while (k != change(0))
    {
        if (k % change(2) == change(1)) res = res * a;
        a = a * a;
        k  = k / change(2);
    }
    return res;
}

Bignum n,m;
Bignum l,r = change(1);

int main()
{
	m.read();n.read();
	while (quick_power(r,m) <= n)
	{
	    l = r;
	    r = r * change(2);
	}
	while (l + change(1) < r)
	{
	    Bignum mid = (l+r)/change(2);
	    if (quick_power(mid,m) <= n)
	        l = mid;
	    else
	        r = mid;
	}
	if (quick_power(r,m) <= n)
		r.write();
	else
		l.write();
    return 0;
}


2023/11/11 15:48
加载中...