958. Euclid's Labour

The Euclidean algorithm can be used to find the greatest common divisor of two positive integers. At each step of the algorithm the smaller number is subtracted from the larger one. The algorithm terminates when the numbers are equal, which is then the greatest common divisor of the original numbers.

For two numbers $n$$n$ and $m$$m$, let $d(n,m)$$d(n, m)$ be the number of subtraction steps used by the Euclidean algorithm for computing the greatest common divisor of $n$$n$ and $m$$m$.

For a number $n$$n$, let $f(n)$$f(n)$ be the positive number $m$$m$ coprime to $n$$n$ that minimizes $d(n,m)$$d(n, m)$. If more than one number attains the minimum, the minimal $m$$m$ is chosen.

For example, at least four steps are needed for computing the GCD of $7$$7$ and any positive number $m$$m$ coprime to $7$$7$. This number of steps is obtained by $m=2,3,4,5$$m=2,3,4,5$, yielding $f(7)=2$$f(7)=2$. You are also given $f(89)=34$$f(89)=34$ and $f(8191)=1856$$f(8191) = 1856$.

Find $f({10}^{12}+39)$$f(10^{12}+39)$.

958. 欧几里得的劳动

欲求解两个正整数的 最大公约数，可以使用 欧几里得算法：不断将两数中较大的一个减去两数中较小的一个，直至二者相等，此时得到的就是原来两个数的最大公约数。

对两个整数 $n,m$$n, m$，我们记 $d(n,m)$$d(n, m)$ 为：使用欧几里得算法计算 $n,m$$n, m$ 的最大公约数时，进行的减法次数。

对某整数 $n$$n$，我们记 $f(n)$$f(n)$ 为：所有与 $n$$n$ 互质的正整数中，能使 $d(n,m)$$d(n, m)$ 取得最小值的正整数 $m$$m$。若有多个符合要求的整数，则取最小的一个 $m$$m$。

例如，对任何与 $7$$7$ 互质的整数 $m$$m$，计算 $gcd(7,m)$$\gcd(7, m)$ 至少需要 $4$$4$ 次减法，且最小次数在 $m=2,3,4,5$$m=2,3,4,5$ 时取到，因而 $f(7)=2$$f(7) = 2$。你已知 $f(89)=34$$f(89)=34$、$f(8191)=1856$$f(8191) = 1856$。

求 $f({10}^{12}+39)$$f(10^{12}+39)$。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。