Lũy thừa

Đ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:

NUS ACM Training

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

Hãy đọc nội quy trước khi bình luận.

-1

HoangNguyen2010 đã bình luận lúc 8, Tháng 12, 2025, 13:46

chặt lồng

-1

HoangNguyen2010 đã bình luận lúc 8, Tháng 12, 2025, 13:46

chặt lần 1 là số mũ

-1

HoangNguyen2010 đã bình luận lúc 8, Tháng 12, 2025, 13:46

chặt lần 1 là số mũ

-1

vominhmanh10 đã bình luận lúc 12, Tháng 10, 2025, 10:41

với cơ số nhỏ nhất là 2 và giới hạn 1e12 thì k chỉ ở khoảng 60 trở xuống là cùng, ta duyệt k ngược cùng tìm kiếm nhị phân cơ số x sao cho x^k <= r rồi mới xét >= l cái đầu tiên thỏa cả hai chính là đáp án

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, r, l, t = 1;
ll check(ll mid, ll k) {
    ll res = 1;
    while (k--) {
        res *= mid;
        if (res > 1e12) return 0;
    }
    if (res <= r) return res;
    return 0;
} 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    while (cin >> l >> r) {
        for (ll k = 64; k >= 1; k--) {
            ll lo = 2, hi = 1e12;
            ll res = 0;
            while (lo < hi) {
                ll mid = (lo + hi + 1) / 2;
                res = check(mid, k);
                if (res > 0) lo = mid;
                else hi = mid - 1;
            }
            if (check(lo, k) >= l) {
                cout << "Case #" << t << ": " << k << "\n";
                t++;
                break;
            }
        }
    }
}

-5

nguyenmanhhung18092012 đã bình luận lúc 4, Tháng 8, 2025, 1:30

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

nguyenmanhhung18092012 đã bình luận lúc 4, Tháng 8, 2025, 1:28

include <bits/stdc++.h>

using namespace std; long long l, r; int t; bool check(long long x, int k, long long r) { __int128 ans = 1; for (int i = 1; i <= k; i++) { ans *= x; if (ans > r) return false; } return true; } void giai(int test) { cin >> l >> r; for (int k = 64; k >= 1; k--) { long long o = 2, m = 1e18, ans = -1; while (o <= m) { long long mid = (o + m) / 2; if (check(mid, k, r)) { if (check(mid, k, l - 1) == false) { cout << "Case #" << t << ": " << k << '\n'; return; } o = mid + 1; } else { m = mid - 1; } } } }

int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin >> t; for (int i = 1; i <= t; i++) { giai(i); } return 0; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

ducbaothan đã bình luận lúc 23, Tháng 7, 2025, 12:36 ← chỉnh sửa →

.

-9
tienguyen3541 đã bình luận lúc 26, Tháng 2, 2025, 14:23
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; }

cout <<"Case #" <<j<<": " << res<<endl; }

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

minhtrivy09 đã bình luận lúc 7, Tháng 8, 2024, 14:28

giải bằng binary search kiểu j v ạ?

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

thaoq8861 đã bình luận lúc 7, Tháng 9, 2024, 2:25

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.

-6

huy_lovely đã bình luận lúc 18, Tháng 2, 2024, 10:31

nếu l và r là 1 và 2 thì in ra bằng bao nhiêu ạ

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.