[leetcode每日一题]4.5

2427. 公因子的数目

提示

简单

20

相关企业

给你两个正整数 a 和 b ，返回 a 和 b 的 公 因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子 。

示例 1：

输入：a = 12, b = 6
输出：4
解释：12 和 6 的公因子是 1、2、3、6 。

示例 2：

输入：a = 25, b = 30
输出：2
解释：25 和 30 的公因子是 1、5 。

提示：

• 1 <= a, b <= 1000

Solution

1.直接遍历到gcd

2.用公式：公因子数目 = ,为第i个质因数的数目

然后使用求质因数的方法求解即可。

class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        n = gcd(a, b) # 待分解的数
        s = Counter()
        x = n
        i = 2
        while i <= x:
            while x%i == 0:
                s[i] += 1
                x //= i
            i += 1
        res = 1
        for v in s.values():
            res *= v + 1
        return res
            

3.遍历到，因为因数是成对出现的，每次加2。

特判一下i*i=n的情况，此时只加1.

class Solution {
public:
    int commonFactors(int a, int b) {
        int ans = 0, g = __gcd(a, b);
        for(int i = 1; i <= g/i; i++) {
            if(a%i == 0 && b%i == 0) {
                ans++;
                if(i*i != g) ans++;
            }
        }
        return ans;
    }
};