当前位置：网站首页>Openjudge noi 1.13 49: calculate logarithm

Openjudge noi 1.13 49: calculate logarithm

2022-06-23 04:41:00 【Junyi_ noip】

【 Topic link 】

OpenJudge NOI 1.13 49: Logarithmic logarithm

【 Topic test site 】

1. High precision

  • High precision times high precision

2. enumeration

【 Their thinking 】

solution 1： enumeration

Because the title says ,x No more than 20, So just enumerate 20 Inside x, See which one to take x Time to satisfy a x ≤ b < a x + 1 a^x\le b < a^{x+1} ax≤b<ax+1 that will do .
High precision numerical comparison is required here 、 High precision times high precision .
a most 100 position ,x The highest 20, The numbers you get a x + 1 a^{x+1} ax+1 Not more than 2100 position .
remember n Is the number a Number of digits , The complexity of the algorithm is ： O ( n x + 1 ) O(n^{x+1}) O(nx+1)

solution 2： Two points

hypothesis x It can be very big , Then we need to use binary search to determine x Value . Use the fast power to find a x a^x ax.
set up l by 1,r by 20, Take the midpoint of each cycle m.

  • If a m + 1 ≤ b a^{m+1} \le b am+1≤b, explain m It's too small ,l It should move right .
  • If b < a m b < a^m b<am, explain m It's bigger ,r Should move left .
  • If a m ≤ b < a m + 1 a^m\le b < a^{m+1} am≤b<am+1, Indicates that the target value is found .

The complexity of the algorithm is O ( l o g x ⋅ l o g x ⋅ n ) O(logx\cdot logx\cdot n) O(logx⋅logx⋅n)

【 Solution code 】

solution 1： enumeration

  • C style ： Array 、 function 
#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： The number on the left  r： The number on the right  
int main()
{
        
    cin >> s1 >> s2;
    toNum(s1, a);
    toNum(s2, b);
    r[0] = 1, r[1] = 1;//r The assignment is 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++ style ： High precision digital class 
#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)// High precision times high precision  
    {
    
        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;
}

solution 2： Two points 

#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)// Determine number of digits 
    {
    
        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)// Fast power   seek a^b 
    {
    
    	HPN c = *this, r("1"); 
		while(b > 0)
		{
    
			if(b % 2 == 1)
				r = r * c;// High precision times high precision  
			c = c * c;// High precision times high precision  
			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)))// Be careful ：^ Operators have lower precedence than relational operators  
            l = m + 1;
        else if(b < (a^m))
            r = m - 1;
        else
        {
    
            cout << m;
            return 0;
        }
    } 
    return 0;
}
原网站

版权声明
本文为[Junyi_ noip]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/174/202206222326304582.html

边栏推荐

猜你喜欢

随机推荐