作业帮 > 综合 > 作业

怎么 超快速 求两个超大数 的 公约数个数 比如 12456789123 和 792378236278 C++ 算法 最

来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：综合作业 时间：2024/04/27 20:42:02
怎么 超快速 求两个超大数 的 公约数个数 比如 12456789123 和 792378236278 C++ 算法 最好
比如现在知道了两个数的最大公约数,现在怎么用C++求 这个最大公约数的 约数个数?比如 考虑两个数：1234567890123 和 1234567890123 这俩数最大公约数是其本身,怎么 超快速 求它的 约数个数?
怎么 超快速 求两个超大数 的 公约数个数 比如 12456789123 和 792378236278 C++ 算法 最
这个问题很简单,分析如下：
1、两个数的公约数的个数,与这两个数最大公约数有关.
假设两个数分别是M、N,最大公约数是X,设M=aX, N=bX那么a和b最大公约数为1.
2、把最大公约数分解成素数的乘积,假设等于A1,A2,...An共计n个素数的乘积.
3、根据分解出的素数,排列组合原理计算公约数个数,需要考虑重复的素数.
注：可以使用短除法求最大公约数.
再问： 你说的第三2、3步怎么解决啊，找到 一个数的 所有不同质因数 不难，难在 怎么处理 重复的素数 比如 2*2*2*3*5*7 我们知道 2、3、5、7(加上1) 共 16个因数，但是 2*2=4， 2*2*2=8 又得考虑 ：4、3、5、7 和 8、3、5、7 这俩组合产生的 因数。这该怎么处理呢？
再答： 假设进行素数分解后得到n1个A1，……，nx个Ax。 那么总个数就是(n1+1)*……*(nx+1)
求两个数字的最大公倍数和最小公约数的算法是怎么样的? 两个数的最小公倍数是300,最小公约数是15,已知其中一个数是75,求另一个数是多少 两个数公约数的个数与这两个数最大公约数的约数的个数相等．______． 同学面试得到的题目,求n（n=100）个数中第5大的数最快速的算法 求c语言2个数最大公约数和最小公倍数的算法 C语言编程中,求两个数的最大公约数和最小公倍数算法是怎样的 C语言程序设:输入两个正整数m和n,求它们所有的公约数,从大到小排列 C语言 n个数中任意取两个数求和的算法 超和最两个字的行书怎么写 求两个数的最大公约数和最小公倍数的算法 求循环队列的元素个数算法,已知front 和 rear,还有容量数,怎么求队列中的循环元素个数? 12和18它们的公约数中选出两个数组成互质数是