[数据结构与算法]OpenJudge NOI 1.13 49:计算对数

【题目链接】

OpenJudge NOI 1.13 49:计算对数

【题目考点】

1. 高精度

• 高精乘高精

2. 枚举

【解题思路】

解法1：枚举

由于题目中说了，x不大于20，所以只需要枚举20以内的x，看取哪一个x时满足$a^x\le b<a^{x+1}$即可。
这里需要高精度数字比较、高精度乘高精度。
a最多100位，x最高20，得到的数字$a^{x+1}$最大不会超过2100位。
记n为数字a的位数，该算法复杂度为：$O(n^{x+1})$

解法2：二分

假设x可以很大，那么需要用二分查找来确定x的值。使用快速幂来求$a^x$。
设l为1，r为20，每次循环取到中点m。

• 如果$a^{m+1}\le b$，说明m取小了，l应该右移。
• 如果$b<a^m$，说明m取大了，r应该左移。
• 如果$a^m\le b<a^{m+1}$，说明找到了目标数值。

该算法的复杂度为$O(logx?logx?n)$

【题解代码】

解法1：枚举

• C风格：数组、函数

#include <bits/stdc++.h>
using namespace std;
#define N 2105
void toNum(char s[], int a[])
{
    a[0] = strlen(s);
    for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0]-i] - '0';
}
void numCpy(int a[], int b[])
{
    for(int i = 0; i <= b[0]; ++i)
        a[i] = b[i];
}
void multi(int a[], int b[])//a *= b
{
    int r[N] = {};
    for(int i = 1; i <= a[0]; ++i)
    {
        int c = 0;
        for(int j = 1; j <= b[0]; ++j)
        {
            r[i+j-1] += c + a[i] * b[j];
            c = r[i+j-1] / 10;
            r[i+j-1] %= 10;      
        }
        r[b[0]+i] += c;
    }
    int ri = a[0] + b[0];
    while(r[ri] == 0 && ri > 1)
        ri--;
    r[0] = ri;
    numCpy(a, r);
} 
int numCmp(int a[], int b[])
{
    if(a[0] > b[0])
        return 1;
    else if(a[0] < b[0])
        return -1;
    else
    {
        for(int i = a[0]; i >= 1; --i)
        {
            if(a[i] > b[i])
                return 1;
            else if(a[i] < b[i])
                return -1;
        }
        return 0;
    }
}
char s1[N], s2[N];
int a[N], b[N], l[N], r[N];//l：左边的数 r：右边的数 
int main()
{    
    cin >> s1 >> s2;
    toNum(s1, a);
    toNum(s2, b);
    r[0] = 1, r[1] = 1;//r赋值为1     
    for(int x = 0; x <= 20; ++x)
    {
        numCpy(l, r);//l = r
        multi(r, a);//r *= a
        if(numCmp(b, l) >= 0 && numCmp(r , b) > 0)//b >= l && r > b
        {
            cout << x;
            return 0;
        }
    }
    return 0;
}

• C++风格：高精度数字类

#include<bits/stdc++.h>
using namespace std;
#define N 2105
struct HPN
{
    int a[N];
    HPN()
    {
        memset(a, 0, sizeof(a));
    }
    HPN(string s)
    {
        memset(a, 0, sizeof(a));
        a[0] = s.length();
        for(int i = 1; i <= a[0]; ++i)
            a[i] = s[a[0]-i] - '0';
    }
    int& operator [] (int i)
    {
        return a[i];
    }
    void operator *= (HPN b)//高精乘高精 
    {
        HPN r;
        for(int i = 1; i <= a[0]; ++i)
        {
            int c = 0;
            for(int j = 1; j <= b[0]; ++j)
            {
                r[i+j-1] += c + a[i] * b[j];
                c = r[i+j-1] / 10;
                r[i+j-1] %= 10;      
            }
            r[b[0]+i] += c;
        }
        int ri = a[0] + b[0];
        while(r[ri] == 0 && ri > 1)
            ri--;
        r[0] = ri;
        *this = r;
    }
    int numCmp(int a[], int b[])
    {
        if(a[0] > b[0])
            return 1;
        else if(a[0] < b[0])
            return -1;
        else
        {
            for(int i = a[0]; i >= 1; --i)
            {
                if(a[i] > b[i])
                    return 1;
                else if(a[i] < b[i])
                    return -1;
            }
            return 0;
        }
    }
    bool operator >= (HPN b)
    {
        return numCmp(a, b.a) >= 0;
    }
    bool operator > (HPN b)
    {
        return numCmp(a, b.a) > 0;
    }
};
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    HPN a(s1), b(s2), l, r("1");
    for(int x = 0; x <= 20; ++x)
    {
        l = r;
        r *= a;
        if(b >= l && r > b)
        {
            cout << x;
            return 0;
        } 
    }
    return 0;
}

解法2：二分

#include<bits/stdc++.h>
using namespace std;
#define N 2105
struct HPN
{
    int a[N];
    HPN()
    {
        memset(a, 0, sizeof(a));
    }
    HPN(string s)
    {
        memset(a, 0, sizeof(a));
        a[0] = s.length();
        for(int i = 1; i <= a[0]; ++i)
            a[i] = s[a[0]-i] - '0';
    }
    int& operator [] (int i)
    {
        return a[i];
    }
    void setLen(int i)//确定数字位数
    {
        while(a[i] == 0 && i > 1)
            i--;
        a[0] = i;
    }
    HPN operator * (HPN b)//r = a * b
    {
        HPN r;
	    for(int i = 1; i <= a[0]; ++i)
	    {
	        int c = 0;
	        for(int j = 1; j <= b[0]; ++j)
	        {
	            r[i+j-1] += a[i]*b[j] + c;
	            c = r[i+j-1] / 10;
	            r[i+j-1] %= 10;
	        }
	        r[i+b[0]] += c;
	    }
	    r.setLen(a[0] + b[0]);
		return r;
    }
    HPN operator ^ (int b)//快速幂 求a^b 
    {
    	HPN c = *this, r("1"); 
		while(b > 0)
		{
			if(b % 2 == 1)
				r = r * c;//高精乘高精 
			c = c * c;//高精乘高精 
			b /= 2;
		}
		return r;
	}
    int numCmp(int a[], int b[])
    {
        if(a[0] > b[0])
            return 1;
        else if(a[0] < b[0])
            return -1;
        else
        {
            for(int i = a[0]; i >= 1; --i)
            {
                if(a[i] > b[i])
                    return 1;
                else if(a[i] < b[i])
                    return -1;
            }
            return 0;
        }
    }
    bool operator >= (HPN b)
    {
        return numCmp(a, b.a) >= 0;
    }
    bool operator < (HPN b)
    {
        return numCmp(a, b.a) < 0;
    }
};
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    HPN a(s1), b(s2);
    int l = 0, r = 20, m;
    while(l <= r)
    {
        m = (l + r) / 2;
        if(b >= (a^(m+1)))//注意：^运算符优先级比关系运算符低 
            l = m + 1;
        else if(b < (a^m))
            r = m - 1;
        else
        {
            cout << m;
            return 0;
        }
    } 
    return 0;
}