Lũy thừa
Xem dạng PDF
Gửi bài giải
Điểm:
0,17 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho ~l~, ~r~ sao cho ~2 \leq l \leq r \leq 10^{12}~. Tìm số ~k~ nguyên dương lớn nhất sao cho tồn tại số nguyên dương ~x~ để ~l \leq x^k \leq r~.
Input
Dòng đầu tiên là số lượng test.
Mỗi dòng tiếp theo chứa hai số nguyên ~l, r~ biểu thị một test.
Output
Đối với mỗi test in ra "Case #" ~+~ số hiệu test ~+~ ": " ~+~ số ~k~ lớn nhất tìm được.
Sample Input
4
5 20
10 12
2 100
1000000000000 1000000000000
Sample Output
Case #1: 4
Case #2: 1
Case #3: 6
Case #4: 12
Bình luận
bài này ta có thể chặt nhị phân theo kiểu này: sopil: mình xin được gợi ý code
include <bits/stdc++.h>
using namespace std; typedef long long ll; const int maxn = 1e6;
define oo (ll)1e12
define fi first
define se second
define ii pair<ll,ll>
define file "TEST"
define fr(i,j,x,n) for (int i = j; i <= n; i += x)
define frn(i,j,x,n) for (int i = j; i >= n; i -= x)
ll po (ll a, ll b){ ll t = 1; while (b){ if (b & 1) t = t * a; a *= a; b >>= 1; } return t; } ll re(ll i, ll l, ll r, ll x, ll y){ ll res = 0; while (l <= r){ ll mid = (l + r) >> 1; if (po(mid,i) > y) r = mid - 1; else{ res = mid; l = mid + 1; } } return res; } int main (){ #ifndef ONLINE_JUDGE ifstream cin(file".INP"); ofstream cout(file".OUT"); #endif ll n; cin >> n; fr(j,1,1,n) { ll x,y; cin >> x >> y; ll res = 0; for (int i = 0; i <= 40; ++i){ ll z = re(i,2,trunc(pow(y,1.0/i))+1,x,y); // if (z == 1) break; ll k = po(z,i); if (k >= x && k <= y) res = i; }
}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
dùng hàm lower bound á
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
l,r>=2 mà
Bài này có thể không cần giải bằng tìm kiếm nhị phân
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Câu này giới hạn test là bao nhiêu vậy ạ
5000 test bạn nhé