Submit solution
Points:
0.17 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem types
Allowed languages
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
Comments
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; }
}
giải bằng binary search kiểu j v ạ?
dùng hàm lower bound á
This comment is hidden due to too much negative feedback. Show it anyway.
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
This comment is hidden due to too much negative feedback. Show it anyway.
Câu này giới hạn test là bao nhiêu vậy ạ
5000 test bạn nhé