LeetCode.每日一题 2427. 公因子的数目

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

题目:公因子的数目

题解:

代码实现:

公约数的个数与公约数之和:

完结撒花：

题目:公因子的数目

题解:

是一题简单题，我们借此来复习下数论里的求最大公约数。

先给出一种解法:暴力枚举

将一个数的所有约数枚举出来,存入数组,之后再用数组中的每一个数,去看看能不能被第二个数整除,若能则答案++

代码实现:

class Solution {
public:
    int commonFactors(int a, int b) {
        vector<int>ans;
        int res=0;
        for(int i=2;i<=a;i++)
        {
            if(a%i==0)ans.push_back(i);
        }
        for(int i=0;i<ans.size();i++)
        {
            if(b%ans[i]==0)res++;
        }   
        return res+1;
    }
};

还有一种方法,即寻找最大公约数,因为若想成为答案的一部分,每个数的约数一定为其最大公约数的因子.所以就转变成了求最大公约数的约数个数问题.

先来看看如何求最大公约数:

int gcd(int a,int b)
    {
        int c=1;
        while(c)
        {
            c=a%b;
            a=b;
            b=c;
        }
        return a;
    }

求出最大公约数后,就寻找其约数个数

这里简化了一下遍历范围,举一个简单的例子:2*3=6 所以2 3都为6的因子,他们都是成对出现的,所以只需要遍历到2的这一半就可以了.2*2!=6 说明其还有另一半,直接答案++即可.

int commonFactors(int a, int b) {
        int d=gcd(a, b);
        int ans=0;
        for(int i=1;i<=d/i;i++)
        {
            if(d%i==0)
            {
                ans++;
                if(i*i!=d)ans++;
            }
        }
        return ans;
    }

公约数的个数与公约数之和:

这里简单复习一下,公约数的个数可以由质因数其指数个数+1再相乘得到

公约数之和可以由质因数每个指数个数相加再相乘得到

质因数可以由此方法得到:先判断这个数能否被i整除,若能就一直除到不能被整除为止,记录次数.若最后x>1,则说明还有另一半没有被找到,则这个另一半即为x

#include<iostream>
using namespace std;
void divide(int x)
{
 
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
        {
            int s=0;
            while(x%i==0)
            {
                x/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
        if(x>1)printf("%d %d\n",x,1);
        puts("");
        return ;
}
int main()
{
    int n=0;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        divide(x);
    }
    return 0;
}