OpenJudge 2739 计算对数

1.链接地址：

http://bailian.openjudge.cn/practice/2739/

2.题目：

总时间限制:

1000ms

内存限制:

65536kB

描述

给定两个正整数a和b。可以知道一定存在整数x，使得

x <= log_ab < x + 1

输出x

输入

第1行是测试数据的组数n，每组测试数据占2行，分别是a和b。每组测试数据之间有一个空行，每行数据不超过100个字符

输出

n行，每组测试数据有一行输出，也就是对应的x。输入数据保证x不大于20

样例输入

3
10000
100000000000110000
999999999999999999999999999999999999999999999999999999999999
1

样例输出

3
2
0

3.思路：

枚举+高精度乘法+高精度比较+数学题

4.代码：

#include <string>
#include 
#include 
#include 
#include 

using namespace std;

string mul(string str1,string str2)
{
    vector<int> v_res(str1.size()+str2.size(),0);
    string::size_type i,j;
    vector<int>::size_type k,p;

    reverse(str1.begin(),str1.end());
    reverse(str2.begin(),str2.end());
    for(i = 0; i != str1.size(); ++i)
    {
        for(j = 0; j != str2.size(); ++j)
        {
            v_res[i+j] += (str1[i]-'0') * (str2[j] - '0');
        }
    }
    for(k = 0; k != v_res.size() - 1; ++k)
    {
        v_res[k+1] += v_res[k] / 10;
        v_res[k] = v_res[k] % 10;
    }

    for(p = v_res.size() - 1; p != -1; --p)
    {
        if(v_res[p] != 0) break;
    }
    if(p == -1) p = 0;

    string s_res(p+1,'0');
    for(k = p; k != -1; --k) s_res[p-k] = char(v_res[k] + '0');
    

    return s_res;

}

int cmp(string str1,string str2)
{
    if(str1.size() != str2.size()) return str1.size() - str2.size();
    int i;
    for(i = 0; i < str1.size(); ++i)
        if(str1[i] != str2[i]) break;
    if(i < str1.size()) return (str1[i] - str2[i]);
    else return 0;
}

int main()
{
    int n;
    cin>>n;

    string a,b;
    int i;
    string x1,x2;
    while(n--)
    {
        cin>>a>>b;
        x1 = "1";
        for(i = 0; i <= 20; ++i)
        {
            x1 = mul(x1,a);
            if(cmp(x1,b) > 0) break;
        }
        cout<endl;
    }
    return 0;
}