简单题的逆袭【牛客tracker 每日一题】
简单题的逆袭
时间限制：1 秒
空间限制：256 MB
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定两个整数x xx和y yy，找出满足方程x k ≤ y x^k \le yxk≤y的最大整数k kk。
输入描述
第一行输入一个整数t ( 1 ≤ t ≤ 300 ) t\ (1 \le t \le 300)t(1≤t≤300)，代表测试数据的组数。
每组输入占一行，包含两个整数x xx和y yy。
数据范围：0 ≤ x , y ≤ 10 18 0 \le x, y \le 10^{18}0≤x,y≤1018。
输出描述
对于每个测试数据，在一行中输出一个整数k kk。
若k kk不存在或者无限大，则输出-1。
示例
示例 1
输入：
2 2 3 0 0输出：
1 -1说明：
- 当x = 2 , y = 3 x = 2,\ y = 3x=2,y=3时，2 1 = 2 ≤ 3 2^1 = 2 \le 321=2≤3，而2 2 = 4 > 3 2^2 = 4 > 322=4>3，所以最大的k kk为1 11。
- 当x = 0 , y = 0 x = 0,\ y = 0x=0,y=0时，对于任意正整数k kk，都有0 k = 0 ≤ 0 0^k = 0 \le 00k=0≤0，因此k kk无限大，输出
-1。
数据范围与提示
- 1 ≤ t ≤ 300 1 \le t \le 3001≤t≤300
- 0 ≤ x , y ≤ 10 18 0 \le x, y \le 10^{18}0≤x,y≤1018
- 注意k kk可能不存在或无限大，此时输出
-1。
解题思路
本题要求对于给定的x xx和y yy，找出最大的整数k kk满足x k ≤ y x^k \le yxk≤y。需要注意边界情况（x = 0 , 1 x = 0, 1x=0,1或y = 0 y = 0y=0）可能导致k kk不存在或无限大，根据题意这些情况应输出− 1 -1−1。
1. 问题等价转化
- 常规情况：当x ≥ 2 x \ge 2x≥2且y ≥ 1 y \ge 1y≥1时，x k x^kxk随k kk增长而指数增长，因此最大的k kk可通过不断将y yy除以x xx来求得，等价于计算⌊ log x y ⌋ \lfloor \log_x y \rfloor⌊logxy⌋。
- 特殊情形分析：
- x = 0 x = 0x=0：0 k = 0 0^k = 00k=0（k ≥ 1 k \ge 1k≥1）。若y ≥ 0 y \ge 0y≥0，对于任意正整数k kk均满足0 ≤ y 0 \le y0≤y，k kk可以无限大；若y < 0 y < 0y<0（本题y ≥ 0 y \ge 0y≥0，不出现），则无解。因此按题意应输出− 1 -1−1。
- x = 1 x = 1x=1：1 k = 1 1^k = 11k=1。若y ≥ 1 y \ge 1y≥1，任意k ≥ 0 k \ge 0k≥0均满足，k kk无限大；若y = 0 y = 0y=0，则1 k = 1 > 0 1^k = 1 > 01k=1>0，无解。综上两种情况均输出− 1 -1−1。
- y = 0 y = 0y=0：需要x k ≤ 0 x^k \le 0xk≤0。当x = 0 x = 0x=0时无限大；当x ≥ 1 x \ge 1x≥1时x k ≥ 1 > 0 x^k \ge 1 > 0xk≥1>0，无解。同样统一输出− 1 -1−1。
- 实现策略：遇到上述特殊情况直接输出− 1 -1−1。对于x ≥ 2 , y ≥ 1 x \ge 2, y \ge 1x≥2,y≥1，初始化答案k = 0 k = 0k=0，反复执行y ← ⌊ y / x ⌋ y \gets \lfloor y / x \rfloory←⌊y/x⌋并令k ← k + 1 k \gets k + 1k←k+1，直到y < x y < xy<x为止，此时的k kk即为最大整数次幂指数。
2. 算法步骤
- 读入测试组数t tt。
- 对于每组( x , y ) (x, y)(x,y)：
- 若x = 0 x = 0x=0或x = 1 x = 1x=1或y = 0 y = 0y=0，输出− 1 -1−1。
- 否则，初始化a n s = 0 ans = 0ans=0。
- 当y ≥ x y \ge xy≥x时，执行y = ⌊ y / x ⌋ y = \lfloor y / x \rfloory=⌊y/x⌋，a n s = a n s + 1 ans = ans + 1ans=ans+1。
- 输出a n s ansans。
3. 复杂度分析
- 时间复杂度：对于每组数据，除法次数不超过log x y ≤ log 2 10 18 ≈ 60 \log_x y \le \log_2 10^{18} \approx 60logxy≤log21018≈60，总复杂度O ( t ⋅ log y ) O(t \cdot \log y)O(t⋅logy)，完全可以接受。
- 空间复杂度：O ( 1 ) O(1)O(1)，仅需常数个变量。
总结
利用指数函数的单调性，通过连续除法快速求出最大整数k kk，同时对x ∈ { 0 , 1 } x \in \{0,1\}x∈{0,1}及y = 0 y = 0y=0这些导致无穷解或无解的特殊情况进行特判，直接输出− 1 -1−1。
代码简要说明
- 判断若
a == 0 || b == 0 || a == 1，输出-1。 - 否则，
ans = 0，循环while (b >= a) { b /= a; ans++; }，输出ans。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cin>>T;while(T--){ll a,b;cin>>a>>b;ll ans=-1;if(a==0||b==0||a==1){cout<<ans<<endl;continue;}ans=0;while(b>=a){b/=a;ans++;}cout<<ans<<endl;}return0;}