Lời giải #1: Đại số (lời giải của tác giả)

Ta thấy rằng \(C^B=A\) khi và chi khi \(log_{10}(C) * B=log_{10}(A)\). Ta có thể tính \(log_{10}(C)\) với một sai số bằng cách tính \(log_{10}(S)+l\), với \(S\) là một số chữ số đầu tiên của \(C\) còn \(l\) là số lượng chữ số còn lại.

Đánh giá sai số: \(log_{10}(A+10^l) \geq log_{10}(A) \geq log_{10}(S)+l = log_{10}(S*10^l) \geq log_{10}(A-10^l)\)

Do đó sai số tối đa sẽ không vượt quá \(log_{10}(A+10^l) - log_{10}(A-10^l) = log_{10}(\frac{A+10^l}{A-10^l}) = log_{10}(1 + \frac{2*10^l}{A+10^l})\).

Ở đây ta chọn \(l = |A|-10\) sẽ đảm bảo AC (\(|A|\) là số chữ số của \(A\)).

Code:

#include<bits/stdc++.h>
using namespace std;

long double getlog10(string s)
{
    long long t = 0;
    for(long long i = 0; i <= 12; i ++)
    {
        if(s.size() > i) t = t * 10 + (s[i] - 48);
        else break;
    }
    return log10(t) + s.size() - min((long long)s.size(), 13LL);
}

int main()
{
    string s;
    long long t;
    cin >> s >> t;
    long double a = getlog10(s) / t;
    for(int i = 1; i <= 100000; i ++)
        if(log10(i) >= a - (1e-12))
        {
            cout << i;
            exit(0);
        }
}

Lời giản #2: Số học (lời giải của bạn LeMinhDuc123 - Lê Minh Đức, THPT Chuyên Sư Phạm, Hà Nội)

Ta thấy điều kiện cần của mệnh đề \(C^B=A\) là \(A\%p=C^B\%p\) với \(p\) là số nguyên tố. Do đó ta nghĩ đến việc chọn một số \(p \le 10^6\) để làm modulo. Nhưng khi ta chọn một vài \(p\) gần \(10^6\), ta thấy được có thể có nhiều hơn một số \(C\). Vì sao lại như thế?

Ta xét một dãy \(a\) được viết theo công thức truy hồi như sau: \(\(a_0=1\)\)\(\(a_i=(a_{i-1} * 2)\%p\)\)

Từ đây ta có thể thấy được một số tính chất sau:

• dãy \(a\) có tính chất tuần hoàn: \(a_{x+p-1}=a_{x}\)
• giả sử \(V=a_x\), ta có \(V^n\%p=a_{nx}\).

Từ đây, ta có thể thấy được \((C_1)^b\%p=(C_2)^b\%p\) khi và chỉ khi \(b|x_1-x_2| \vdots p-1\), với \(x_1, x_2\) là các số nguyên nhỏ nhất sao cho \(C_1=x_1, C_2=x_2\). Từ đây đánh giá được \(0 < |x_1-x_2| < p-1\). (Đến đây thấy bịp quá chọn luôn \(p=10^9+7\) và AC :>).

Code:

#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long b;

long long binpowmod(long long a, long long x)
{
    if(x == 0) return 1;
    if(x == 1) return a;
    long long t = binpowmod(a, x / 2);
    return ((t * t) % MOD * binpowmod(a, x % 2)) % MOD;
}

string s;

long long getmod()
{
    long long t = 0;
    for(int i = 0; i < s.size(); i ++)
        t = ((t * 10) + (s[i] - '0')) % MOD;
    return t;
}

int main()
{
    cin >> s >> b;
    long long t = getmod();
    for(int i = 1; i <= 1e5; i ++)
        if(binpowmod(i, b) == t)
        {
            cout << i;
            exit(0);
        }
}