2022 IMO Shortlist N3

Let $a>1$ be a positive integer, and let $d>1$ be a positive integer coprime to $a$. Let $x_{1}=1$ and, for $k \geq 1$, define $$x_{k+1}= \begin{cases}x_{k}+d & \text { if } a \text { doesn't divide } x_{k} \\ x_{k} / a & \text { if } a \text { divides } x_{k}\end{cases}$$ Find the greatest positive integer $n$ for which there exists an index $k$ such that $x_{k}$ is divisible by $a^{n}$. (Croatia)

令$a>1$ 为正整数，并令$d>1$ 为与$a$ 互质的正整数。令 $x_{1}=1$ 且对于 $k \geq 1$，定义 $$x_{k+1}= \begin{cases}x_{k}+d & \text { if } a \text { 不除 } x_{k} \\ x_{k} / a & \text { if } a \text { 除 } x_{k}\end{cases}$$ 找到最大正整数 $n$存在一个索引 $k$，使得 $x_{k}$ 可以被 $a^{n}$ 整除。 (克罗地亚)