2427-公因子的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你两个正整数 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

方法一：枚举到较小值

思路与算法

由于 a 和 b 的公因子一定不会超过 a 和 b，因此我们只需要在 [1, \min(a, b)] 中枚举 x，并判断 x 是否为公因子即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int commonFactors(int a, int b) {
        int ans = 0;
        for (int x = 1; x <= min(a, b); ++x) {
            if (a % x == 0 && b % x == 0) {
                ++ans;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int commonFactors(int a, int b) {
        int ans = 0;
        for (int x = 1; x <= Math.min(a, b); ++x) {
            if (a % x == 0 && b % x == 0) {
                ++ans;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int CommonFactors(int a, int b) {
        int ans = 0;
        for (int x = 1; x <= Math.Min(a, b); ++x) {
            if (a % x == 0 && b % x == 0) {
                ++ans;
            }
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        ans = 0
        for x in range(1, min(a, b) + 1):
            if a % x == 0 and b % x == 0:
                ans += 1
        return ans
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int commonFactors(int a, int b) {
    int ans = 0;
    int c = MIN(a, b);
    for (int x = 1; x <= c; ++x) {
        if (a % x == 0 && b % x == 0) {
            ++ans;
        }
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
var commonFactors = function(a, b) {
    let ans = 0;
    for (let x = 1; x <= Math.min(a, b); ++x) {
        if (a % x === 0 && b % x === 0) {
            ++ans;
        }
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func commonFactors(a int, b int) int {
    m := min(a, b)
    ans := 0
    for i := 1; i <= m; i++ {
        if a%i == 0 && b%i == 0 {
            ans++
        }
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是给定输入 a 和 b 的范围。

  • 空间复杂度：O(1)。

方法二：枚举到最大公约数

思路与算法

x 是 a 和 b 的公因子，当且仅当 x 是 a 和 b 的最大公约数的因子。因此，我们可以首先求出 a 和 b 的最大公约数 c = \gcd(a, b)，再枚举 c 的因子个数。

我们可以使用类似方法一种的遍历，对于 [1, c] 中的整数依次进行枚举，时间复杂度为 O(c)。我们也可以进行一些优化，因子一定是成对出现的：如果 x 是 c 的因子，那么 \dfrac{c}{x 一定也是 c 的因子。因此，我们可以仅对 [1, \lfloor \sqrt{c} \rfloor] 中的整数依此进行枚举，如果枚举到 x 是 c 的因子，并且 x \neq \dfrac{c}{x（即 x^2 \neq c），那么答案额外增加 1。这样一来，时间复杂度可以降低至 O(\sqrt{c})。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int commonFactors(int a, int b) {
        int c = gcd(a, b), ans = 0;
        for (int x = 1; x * x <= c; ++x) {
            if (c % x == 0) {
                ++ans;
                if (x * x != c) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int commonFactors(int a, int b) {
        int c = gcd(a, b), ans = 0;
        for (int x = 1; x * x <= c; ++x) {
            if (c % x == 0) {
                ++ans;
                if (x * x != c) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    public int gcd(int a, int b) {
        while (b != 0) {
            a %= b;
            a ^= b;
            b ^= a;
            a ^= b;
        }
        return a;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int CommonFactors(int a, int b) {
        int c = GCD(a, b), ans = 0;
        for (int x = 1; x * x <= c; ++x) {
            if (c % x == 0) {
                ++ans;
                if (x * x != c) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    public int GCD(int a, int b) {
        while (b != 0) {
            a %= b;
            a ^= b;
            b ^= a;
            a ^= b;
        }
        return a;
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def commonFactors(self, a: int, b: int) -> int:
        c, ans = gcd(a, b), 0
        x = 1
        while x * x <= c:
            if c % x == 0:
                ans += 1
                if x * x != c:
                    ans += 1
            x += 1
        return ans
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int gcd(int a, int b) {
    while (b != 0) {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return a;
}

int commonFactors(int a, int b) {
    int c = gcd(a, b), ans = 0;
    for (int x = 1; x * x <= c; ++x) {
        if (c % x == 0) {
            ++ans;
            if (x * x != c) {
                ++ans;
            }
        }
    }
    return ans;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var commonFactors = function(a, b) {
    let c = gcd(a, b), ans = 0;
    for (let x = 1; x * x <= c; ++x) {
        if (c % x === 0) {
            ++ans;
            if (x * x !== c) {
                ++ans;
            }
        }
    }
    return ans;
}

const gcd = (a, b) => {
    while (b !== 0) {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }
    return a;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func commonFactors(a int, b int) int {
	g := gcd(a, b)
	ans := 0
	for i := 1; i*i <= g; i++ {
		if g%i == 0 {
			ans++
			if i*i < g {
				ans++
			}
		}
	}
	return ans
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

复杂度分析

  • 时间复杂度：O(\sqrt{n})，其中 n 是给定输入 a 和 b 的范围。需要注意的是，求解 a 和 b 最大公约数需要 O(\log n) 的时间，但其渐进意义下小于 O(\sqrt{n})，因此可以省略。

  • 空间复杂度：O(1)。

 Comments
On this page
2427-公因子的数目