P1029. 最大公约数和最小公倍数问题

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 350 阅读时长 ≈ 1 分钟

考点

  • 最大公约数

题解

见思路

思路

枚举约数

由于\(PQ=xy\)，且\(P\shortmid y\)，所以枚举y的所有约数；约数是成对出现的，每次可以得到两个约数p和y/p

然后用xy/约数得到q，再判断p和q的最大公约数是否满足条件即可，时间复杂度为\(O\left( \sqrt{y} \right)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  int x, y, ans = 0;
  cin >> x >> y;
  ll mul = x * y;
  // 枚举y的约数，可以是p也可以是y/p
  for (int p = 1; p <= y / p; ++p) {
    if (y % p == 0) {
      if (gcd(p, mul / p) == x) ++ans;
      if (p != y / p && gcd(y / p, x * p) == x) ++ans;
    }
  }
  cout << ans;
  return 0;
}

枚举倍数

由于\(x\shortmid p\)，所以可以通过枚举x的倍数，来枚举p，显然p不会超过最小公倍数y

但是这样做的时间复杂度是\(O\left( \frac{y}{x} \right)\)，比枚举约数的方式复杂度高了很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  int x, y, ans = 0;
  cin >> x >> y;
  ll mul = x * y;
  // 通过枚举x的倍数的方式枚举p，肯定不会超过最小公倍数y
  for (int p = x; p <= y; p += x) {
    if (mul % p == 0) {
      int q = mul / p;
      if (gcd(p, q) == x) ++ans;
    }
  }
  cout << ans;
  return 0;
}