猫猫与数列时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述猫猫发现了一个数列a 1 p , a 2 q , a n a n − 2 a n − 1 ( n ≥ 3 ) a_1 p,\quad a_2 q,\quad a_n a_{n-2}^{a_{n-1}}\ (n \ge 3)a1​p,a2​q,an​an−2an−1​​(n≥3)为了防止数据溢出猫猫想让你找到最大的正整数n nn使得a n ≤ M a_n \le Man​≤M其中M 10 18 M 10^{18}M1018。可以证明一定有解。输入描述一行包含两个正整数p pp和q qq。数据范围2 ≤ p , q ≤ 10 9 2 \le p, q \le 10^92≤p,q≤109。输出描述一行输出一个整数表示满足a n ≤ 10 18 a_n \le 10^{18}an​≤1018的最大正整数n nn。示例示例 1输入2 2输出5说明数列为2 , 2 , 2 2 4 , 2 4 16 , 16 4 65536 , … 2,\ 2,\ 2^24,\ 2^416,\ 16^465536,\ \dots2,2,224,2416,16465536,…其中a 6 65536 16 10 18 a_6 65536^{16} 10^{18}a6​65536161018因此最大的n nn为5 55。示例 2输入999999998 2输出3示例 3输入10 18输出3数据范围与提示2 ≤ p , q ≤ 10 9 2 \le p, q \le 10^92≤p,q≤109M 10 18 M 10^{18}M1018数列增长非常快建议使用高精度乘法或对数比较来判断是否溢出。解题思路本题要求直接按照递推式生成数列并在每一项超过10 18 10^{18}1018时停止。由于数列增长极快实际迭代次数非常少因此可以在循环中模拟幂运算并实时检测溢出找到最大满足条件的项数。1. 问题等价转化递推计算已知a 1 p a_1 pa1​pa 2 q a_2 qa2​q对n ≥ 3 n \ge 3n≥3有a n a n − 2 a n − 1 a_n a_{n-2}^{a_{n-1}}an​an−2an−1​​。题目要求最大的正整数n nn使得a n ≤ M a_n \le Man​≤M其中M 10 18 M 10^{18}M1018。直接模拟从n 2 n2n2开始迭代。每一轮计算a n 1 p q a_{n1} p^qan1​pq其中p a n − 1 p a_{n-1}pan−1​q a n q a_nqan​判断是否超过M MM。溢出处理由于指数q qq可能达到10 18 10^{18}1018级别不能直接使用快速幂或调用pow。可以采用逐次乘法并检查是否即将超出M MM的方式设当前累积结果为r rr初始r p r prp。每乘一次p pp都相当于r ← r × p r \leftarrow r \times pr←r×p在乘法前检查r M / p。若成立则说明再乘一次就会超过M MM即p q M p^q MpqM此时当前n nn就是答案。2. 算法步骤读入p , q p, qp,q令n 2 n 2n2表示已经满足前两项。循环令r p。用循环执行q-1次乘法每次先检查r INF / pINF 1e18。若成立输出n并结束程序否则执行r * p。成功得到r p^q且未溢出则更新p qq rn n 1。最终当发现溢出时输出的n即为满足a n ≤ M a_n \le Man​≤M的最大项数。3. 正确性与复杂度正确性保证每次乘法前用除法预判溢出避免实际越界同时由于数列第n nn项都会由前两项唯一确定循环维护的p , q p,qp,q始终对应最新的两项。时间复杂度虽然指数q qq可能很大但底数p ≥ 2 p \ge 2p≥2p q p^qpq会在极少的乘法次数内超过10 18 10^{18}1018例如2 60 10 18 2^{60} 10^{18}2601018因此内层乘法循环实际执行的次数不超过60 6060次。总迭代轮数也极少总复杂度O ( 1 ) O(1)O(1)级别。空间复杂度O ( 1 ) O(1)O(1)仅需少量变量。总结利用“增长极快”的性质直接模拟幂的乘法过程并通过除法预判避免溢出。每轮迭代最多进行约60 6060次乘法因此算法极快能够正确处理10 9 10^9109范围的数据。代码简要说明常量定义INF 1e18作为上限M MM。初始化读入p , q p,qp,qn2。主循环r pfor (i 1; i q; i)若r INF / p说明p^q M输出n并返回否则r * p更新p qq rn。输出输出最大满足条件的n。代码内容#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 p,q;cinpq;ll n2;while(true){ll rp;for(ll i1;iq;i){if(rINF/p){coutn;return0;}r*p;}pq;qr;n;}}