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

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/08 00:16:21

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

怎么 超快速 求两个超大数 的 公约数个数 比如 12456789123 和 792378236278 C++ 算法 最好比如现在知道了两个数的最大公约数,现在怎么用C++求 这个最大公约数的 约数个数?比如 考虑两个数:1234567
这个问题很简单,分析如下:
1、两个数的公约数的个数,与这两个数最大公约数有关.
假设两个数分别是M、N,最大公约数是X,设M=aX, N=bX那么a和b最大公约数为1.
2、把最大公约数分解成素数的乘积,假设等于A1,A2,...An共计n个素数的乘积.
3、根据分解出的素数,排列组合原理计算公约数个数,需要考虑重复的素数.
注:可以使用短除法求最大公约数.