简单题的逆袭【牛客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 3x2,y3时2 1 2 ≤ 3 2^1 2 \le 3212≤3而2 2 4 3 2^2 4 32243所以最大的k kk为1 11。当x 0 , y 0 x 0,\ y 0x0,y0时对于任意正整数k kk都有0 k 0 ≤ 0 0^k 0 \le 00k0≤0因此k kk无限大输出-1。数据范围与提示1 ≤ t ≤ 300 1 \le t \le 3001≤t≤3000 ≤ 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, 1x0,1或y 0 y 0y0可能导致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⌊logx​y⌋。特殊情形分析x 0 x 0x00 k 0 0^k 00k0k ≥ 1 k \ge 1k≥1。若y ≥ 0 y \ge 0y≥0对于任意正整数k kk均满足0 ≤ y 0 \le y0≤yk kk可以无限大若y 0 y 0y0本题y ≥ 0 y \ge 0y≥0不出现则无解。因此按题意应输出− 1 -1−1。x 1 x 1x11 k 1 1^k 11k1。若y ≥ 1 y \ge 1y≥1任意k ≥ 0 k \ge 0k≥0均满足k kk无限大若y 0 y 0y0则1 k 1 0 1^k 1 01k10无解。综上两种情况均输出− 1 -1−1。y 0 y 0y0需要x k ≤ 0 x^k \le 0xk≤0。当x 0 x 0x0时无限大当x ≥ 1 x \ge 1x≥1时x k ≥ 1 0 x^k \ge 1 0xk≥10无解。同样统一输出− 1 -1−1。实现策略遇到上述特殊情况直接输出− 1 -1−1。对于x ≥ 2 , y ≥ 1 x \ge 2, y \ge 1x≥2,y≥1初始化答案k 0 k 0k0反复执行y ← ⌊ y / x ⌋ y \gets \lfloor y / x \rfloory←⌊y/x⌋并令k ← k 1 k \gets k 1k←k1直到y x y xyx为止此时的k kk即为最大整数次幂指数。2. 算法步骤读入测试组数t tt。对于每组( x , y ) (x, y)(x,y)若x 0 x 0x0或x 1 x 1x1或y 0 y 0y0输出− 1 -1−1。否则初始化a n s 0 ans 0ans0。当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 1ansans1。输出a n s ansans。3. 复杂度分析时间复杂度对于每组数据除法次数不超过log ⁡ x y ≤ log ⁡ 2 10 18 ≈ 60 \log_x y \le \log_2 10^{18} \approx 60logx​y≤log2​1018≈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 0y0这些导致无穷解或无解的特殊情况进行特判直接输出− 1 -1−1。代码简要说明判断若a 0 || b 0 || a 1输出-1。否则ans 0循环while (b a) { b / a; ans; }输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--){ll a,b;cinab;ll ans-1;if(a0||b0||a1){coutansendl;continue;}ans0;while(ba){b/a;ans;}coutansendl;}return0;}