dhru商城网站建设,网站建设督查工作主持词,android软件开发工程师,营销方法有哪几种Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 目录
题目:公因子的数目
题解:
代码实现: 公约数的个数与公约数之和:
完结撒花 题目:公因子的数目 题解:
是一题简单题我们借此来复习下数论里的求最大公约数。
先给出一种解法:暴力枚举
将一个数的所有约数枚举出来,存入数组,之后再用数组中的每一个数,去看看能不能被第二个数整除,若能则答案
代码实现:
class Solution {
public:int commonFactors(int a, int b) {vectorintans;int res0;for(int i2;ia;i){if(a%i0)ans.push_back(i);}for(int i0;ians.size();i){if(b%ans[i]0)res;} return res1;}
}; 还有一种方法,即寻找最大公约数,因为若想成为答案的一部分,每个数的约数一定为其最大公约数的因子.所以就转变成了求最大公约数的约数个数问题.
先来看看如何求最大公约数:
int gcd(int a,int b){int c1;while(c){ca%b;ab;bc;}return a;}
求出最大公约数后,就寻找其约数个数
这里简化了一下遍历范围,举一个简单的例子:2*36 所以2 3都为6的因子,他们都是成对出现的,所以只需要遍历到2的这一半就可以了.2*2!6 说明其还有另一半,直接答案即可.
int commonFactors(int a, int b) {int dgcd(a, b);int ans0;for(int i1;id/i;i){if(d%i0){ans;if(i*i!d)ans;}}return ans;} 公约数的个数与公约数之和:
这里简单复习一下,公约数的个数可以由质因数其指数个数1再相乘得到 公约数之和可以由质因数每个指数个数相加再相乘得到 质因数可以由此方法得到:先判断这个数能否 被i整除,若能就一直除到不能被整除为止,记录次数.若最后x1,则说明还有另一半没有被找到,则这个另一半即为x
#includeiostream
using namespace std;
void divide(int x)
{for(int i2;ix/i;i)if(x%i0){int s0;while(x%i0){x/i;s;}printf(%d %d\n,i,s);}if(x1)printf(%d %d\n,x,1);puts();return ;
}
int main()
{int n0;cinn;while(n--){int x;cinx;divide(x);}return 0;
}
完结撒花 本篇博客的内容【LeetCode.每日一题 2427. 公因子的数目】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
