两个数字的 gcd 其中一个太大
gcd of two numbers one of them is too large
我正在做一个要求计算 gcd(a-b,a^n+b^n)%(10^9+7) 的问题，其中 a、b、n 可以大到 10^12。
对于非常小的数，我能够解决 a、b 和 n 的问题，费马定理似乎也不起作用，我得出的结论是，如果 a、b 互质，那么这将始终给我gcd as 2 但其余的我无法得到它？
我只需要一点提示就可以得到大量的 gcd 是我做错了什么？我也尝试过 x^y 通过在每一步取模来找到 gcd，但这也没有用。
只需要方向，我就会让路。
提前致谢。
您是正确的，a^n + b^n 太大而无法计算，并且在每个步骤中使用 mod 10^9 + 7 并不能提供计算答案的方法。但是，您仍然可以使用 mod 方求幂，方法是对 不同的 mod 求方，即 a-b
主要观察：
1) gcd(a-b,a^n + b^n) = gcd(d,a^n + b^n) where d = abs(a-b)
2) gcd(d,a^n + b^n) = gcd(d,r) where r = (a^n + b^n) % d
3) r can be feasibly computed with modular exponentiation by squaring
1)的要点是不同的编程语言在mod运算符中处理负数的约定不同。取绝对值可以避免这种复杂情况，尽管在数学上它并没有什么不同。关键思想是做欧几里德算法的第一步计算gcds是完全可行的。您所需要的只是两个数中较大数除以较小数的余数。完成第一步后，所有的数字都在可行范围内。
我正在做一个要求计算 gcd(a-b,a^n+b^n)%(10^9+7) 的问题，其中 a、b、n 可以大到 10^12。
对于非常小的数，我能够解决 a、b 和 n 的问题，费马定理似乎也不起作用，我得出的结论是，如果 a、b 互质，那么这将始终给我gcd as 2 但其余的我无法得到它？
我只需要一点提示就可以得到大量的 gcd 是我做错了什么？我也尝试过 x^y 通过在每一步取模来找到 gcd，但这也没有用。
只需要方向，我就会让路。
提前致谢。
您是正确的，a^n + b^n 太大而无法计算，并且在每个步骤中使用 mod 10^9 + 7 并不能提供计算答案的方法。但是，您仍然可以使用 mod 方求幂，方法是对 不同的 mod 求方，即 a-b
主要观察：
1) gcd(a-b,a^n + b^n) = gcd(d,a^n + b^n) where d = abs(a-b)
2) gcd(d,a^n + b^n) = gcd(d,r) where r = (a^n + b^n) % d
3) r can be feasibly computed with modular exponentiation by squaring
1)的要点是不同的编程语言在mod运算符中处理负数的约定不同。取绝对值可以避免这种复杂情况，尽管在数学上它并没有什么不同。关键思想是做欧几里德算法的第一步计算gcds是完全可行的。您所需要的只是两个数中较大数除以较小数的余数。完成第一步后，所有的数字都在可行范围内。