怎么超快速求两个超大数的公约数个数比如12456789123和792378236278C++算法最好比如现在知道了两个数的最大公约数,现在怎么用C++求这个最大公约数的约数个数?比如考虑两个数：1234567

Question

怎么 超快速 求两个超大数 的 公约数个数 比如 12456789123 和 792378236278 C++ 算法 最好
比如现在知道了两个数的最大公约数,现在怎么用C++求 这个最大公约数的 约数个数?比如 考虑两个数：1234567890123 和 1234567890123 这俩数最大公约数是其本身,怎么 超快速 求它的 约数个数?

Answer 1

这个问题很简单,分析如下：1、两个数的公约数的个数,与这两个数最大公约数有关. 假设两个数分别是M、N,最大公约数是X,设M=aX, N=bX那么a和b最大公约数为1.2、把最大公约数分解成素数的乘积,假设等于A1,A2,...An...