P1635 跳跃网页链接P1635 跳跃题目背景NOIP 即将迎来周年华诞。在这一个春秋的历程里NOIP 领导全国 oier建设高效、稳定、快捷、开放的社会主义现代化 OI。在新的一年里YZOJ 将再接再厉积极探寻成长之路更好地为广大 oier 服务。题目描述青蛙小 C 听说 NOIP 要办周年庆比赛兴冲冲得来到了 Z 市初始时他在坐标x 0 x_0x0​处小 C 是一只善于跳跃的青蛙若当前他处在坐标x xx处每一次跳跃他可以跳到4 x 3 4x34x3或8 x 7 8x78x7处且由于体力原因他最多能跳100000 100000100000次。根据 Z 市的传说坐标位置为10 9 7 10^971097的整数倍的位置如10 9 7 , 2 × 10 9 14 10^97,2\times 10^9141097,2×10914可以传送到 YZOJ。小 C 想知道最少跳几次能传送到 YZOJ。输入格式输入的第一行包含一个整数x 0 x_0x0​表示青蛙的初始位置保证x 0 x_0x0​在的范围在[ 1 , 10 9 6 ] [1,10^96][1,1096]。输出格式输出一个整数表示最少所需步数若在100000 100000100000步内还无法传送到 YZOJ则输出− 1 -1−1。输入输出样例 #1输入 #1125000000输出 #11解题思路本题是数学变换与同余求解问题。青蛙每次跳跃可看作对当前位置施加两种线性变换之一目标位置是10 9 7 10^971097的整数倍。通过将两种跳跃统一为更小的基本变换并利用模运算将目标转化为使基本变换迭代后余数为0 00可以高效地求出最少跳跃次数。1. 问题等价转化记M 10 9 7 M 10^97M1097。定义基本变换f ( x ) 2 x 1 f(x) 2x 1f(x)2x1。一次跳跃4 x 3 4x34x3相当于连续执行两次f fff ( f ( x ) ) 2 ( 2 x 1 ) 1 4 x 3 f(f(x)) 2(2x1)1 4x3f(f(x))2(2x1)14x3一次跳跃8 x 7 8x78x7相当于连续执行三次f fff ( f ( f ( x ) ) ) 8 x 7 f(f(f(x))) 8x7f(f(f(x)))8x7目标位置是M MM的整数倍即最终坐标对M MM取模为0 00。因此问题转化为找到最小的非负整数k kk使得f k ( x 0 ) ≡ 0 ( m o d M ) f^k(x_0) \equiv 0 \pmod Mfk(x0​)≡0(modM)其中f k f^kfk表示f ff迭代k kk次。2. 求解最少基本变换次数由于M MM是质数且x 0 x_0x0​范围在[ 1 , M − 1 ] [1, M-1][1,M−1]可以直接从x 0 x_0x0​开始不断应用f ff即a ← ( 2 a 1 ) m o d M a \gets (2a1) \bmod Ma←(2a1)modM直到a 0 a0a0。每应用一次f ff就对应一个基本步记录总次数i ii。因为一次跳跃最多对应3 33次基本步青蛙最多跳10 5 10^5105次所以基本步数最多只需要检查3 × 10 5 10 3\times 10^5 103×10510次。若在该范围内仍不能使余数为0 00则说明10 5 10^5105步内无法到达目标。3. 将基本步数换算为最少跳跃次数已知需要i ii次基本步。每次跳跃可以使用两种“步长”4 x 3 4x34x3消耗2 22次基本步8 x 7 8x78x7消耗3 33次基本步。为了用最少的跳跃次数凑够i ii次基本步优先使用消耗3 33次基本步的跳跃。若i m o d 3 0 i \bmod 3 0imod30则全部用8 x 7 8x78x7跳跃次数为i / 3 i/3i/3。若i m o d 3 1 i \bmod 3 1imod31或2 22则用⌊ i / 3 ⌋ \lfloor i/3 \rfloor⌊i/3⌋次8 x 7 8x78x7和一次4 x 3 4x34x3当余数为2 22时恰好弥补余数为1 11时多出一次基本步但跳跃次数仍为⌊ i / 3 ⌋ 1 \lfloor i/3 \rfloor 1⌊i/3⌋1。因此最少跳跃次数统一为⌈ i / 3 ⌉ \lceil i/3 \rceil⌈i/3⌉。4. 算法步骤读入初始位置x 0 x_0x0​。令a x 0 a x_0ax0​i 0 i 0i0。循环执行a ( 2 a 1 ) m o d M a (2a 1) \bmod Ma(2a1)modMi i 1 i i 1ii1直到a 0 a 0a0或i 3 × 10 5 10 i 3\times 10^5 10i3×10510。若i 3 × 10 5 i 3\times 10^5i3×105说明无法在10 5 10^5105步内到达输出− 1 -1−1。否则计算a n s ⌈ i / 3 ⌉ ( i 2 ) / 3 ans \lceil i/3 \rceil (i2)/3ans⌈i/3⌉(i2)/3整数除法。若a n s 10 5 ans 10^5ans105输出− 1 -1−1否则输出a n s ansans。5. 复杂度分析时间复杂度最坏循环3 × 10 5 3\times 10^53×105次每次O ( 1 ) O(1)O(1)总复杂度O ( 10 5 ) O(10^5)O(105)足够快。空间复杂度仅使用几个变量O ( 1 ) O(1)O(1)。总结将两种跳跃统一为基本变换f ( x ) 2 x 1 f(x)2x1f(x)2x1把目标转化为模M MM意义下使f ff迭代到0 00。求出所需最少基本步数后再根据步长2 22和3 33的组合转换为最少跳跃次数。整个过程利用了模运算和线性变换的性质简洁高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll LIM100000;ll n,i,a,ans;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);for(i0,an;iLIM*310;a((a1)1)%mod,i)if(a0)break;if(i%30)ansi/3;if(i%31||i%32)ansi/31;if(ansLIM)ans-1;printf(%lld\n,ans);return0;}