LC.P2427[公因子的数目]

方法一：枚举

1
2
3
4
5
6
7
8
9
class Solution {
    public int commonFactors(int a, int b) {
        int ans = 0;
        for (int i = 1; i <= Math.min(a, b); ++i) {
            if (a % i == 0 && b % i == 0) ++ans;
        }
        return ans;
    }
}
  • 时间复杂度：$O(min(a,b))$
  • 空间复杂度：$O(1)$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int commonFactors(int a, int b) {
        int ans = 0;
        int g = gcd(a, b);
        for (int i = 1; i <= g; ++i) {
            if (g % i == 0) ++ans;
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
  • 时间复杂度：$O(min(a,b))$
  • 空间复杂度：$O(1)$

方法三：枚举最大公因数的因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int commonFactors(int a, int b) {
        int ans = 0;
        int g = gcd(a, b);
        for (int i = 1; i * i <= g; ++i) {
            if (g % i == 0) {
                ++ans;
                if (i * i != g) ++ans; // x != c/x
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
  • 时间复杂度：$O( \sqrt {min(a,b)} )$
  • 空间复杂度：$O(1)$