Lũy thừa

View as PDF
Submit solution
Points: 0.17 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
NUS ACM Training
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

Please read the guidelines before commenting.


  • -2
    tienguyen3541  commented on Feb. 26, 2025, 2:23 p.m.

    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 #" <&lt;j<<": " << res<&lt;endl;
}

    }


  • -4
    minhtrivy09  commented on Aug. 7, 2024, 2:28 p.m.

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


    • -4
      thaoq8861  commented on Sept. 7, 2024, 2:25 a.m.

      dùng hàm lower bound á


  • -8
    huy_lovely  commented on Feb. 18, 2024, 10:31 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      An212  commented on March 13, 2024, 3:00 p.m.

      l,r>=2 mà


  • 0
    baolam01662052827  commented on July 11, 2023, 6:06 p.m.

    Bài này có thể không cần giải bằng tìm kiếm nhị phân


  • -142
    hbphuc2009  commented on July 12, 2022, 1:05 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 11
    FuzZefer  commented on Sept. 1, 2021, 3:37 p.m.

    Câu này giới hạn test là bao nhiêu vậy ạ


    • 18
      leduykhongngu  commented on Sept. 30, 2021, 3:40 p.m.

      5000 test bạn nhé