假定每次整除平均需要 $q$ 次，复杂度 $O(qn),qn\ge {10}^9$，显然不行。 出题人友好的用第三组样例提示了数组的循环性（我咋知道，他又没给完），加之题目背景和 $3n+1$ 问题有关，所以也能和循环扯上关系，不妨从这个角度考虑。 既然题目背景有暗示，多测几组数据也能看出来（反正我是没看出来），这个数会在不断地迭代过程中变为 1，然后在 1 到 $y-1$ 中循环。 下面推一下官解的公式：

1. 第一步优化归一后的结果求解，这个循环的周期是 $y-1$，现在还剩 $k$ 次计算，整个变化的数组长这样

$$\{x,\cdots ,1,\cdots ,y-1,1\cdots ,y-1\}$$

众所周知（我还真不是很知），$kmody-1$ 的取值是 $\{0,\cdots ,y-2\}$ ，所对应的值应当是 $\{1,\cdots ,y-2\}$，所以将剩余 $k$ 次运算转化为结果就是（前提是 $k$ 次运算后能够将给的 $x$ 归一）

$$ans=1+kmod(y-1)$$

不能归一的话怎么办呢，最简单的就是直接把这个时候的 $x$ 输出，但是官解压行了，因为这时候 $k=0$，显然有

$$ans=x+0mod(y-1)=x$$

合并两类，推出最终公式：

$$ans=x+kmod(y-1)$$

2. 只做第一步优化连样例都过不了，因为数据给大之后凑整除需要的累加次数也会很大，很容易就超了，所以还要优化累加操作。 比如要让 $16$ 被 $5$ 整除，很容易想到要凑 $20$，也就是说找到 $5$ 在 $16$ 后的一个倍数，首先确定 $5$ 在 $16$ 大约是 $\frac{16}{5}$ 倍，显然下一个倍数就是 $\lceil \frac{16}{5}\rceil \times 5=20$，也就是说，每次直接加上

$$op=\lceil \frac{x}{y}\rceil \times y-x$$

就行了。 当然如果这里使用 ceil 做取整运算还是超，因为这玩意其实是 double __cdecl ceil(double _X);，并非是对整型的运算，算多了效率挺低，因此数学代换一下就成了（当然这个除是整除）：

$$op=(\frac{x}{y}+1)\times y-x$$

第一个公式单从数学意义上来说，对于 $y\in Z,op\ge x\ge 0$ 好像没问题，但不要忘了这是整除，会出现 $\frac{x}{y}=0$ 的情况，因此要确保每次至少加 $1$，同时还要确保每次累加操作不超过当前的剩余操作次数 $k$。 由于每次加都至少可以整除一次，所以每次操作至少将当前数减少

$$\lceil \frac{x+1}{y}\rceil ,y\ge 2$$

显然时间复杂度优于二分，为 $O(\log n)$。