Hướng dẫn cho Căn bậc B của A
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
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 - 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);
}
}
Bình luận
Cách khác ko nhờ hint:
mày nhờ hint mình mới ac đc ko thôi thì hetcuu rồi
.
ngôn ngữ gì vậy