题解：【YACS 2022年 1 月月赛丙组】平衡括号

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

512 字

3 分钟

题解：【YACS 2022年 1 月月赛丙组】平衡括号

2024-06-03

2026-10-03

题解

C艹

浏览量加载中...

提供一种快速做法（31ms）~

首先，枚举是必须的，但是可以快速枚举。

优化 1：众所周知 $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$ ，所以我们只需要枚举 $a$ 就好了。

优化 2： $a$ 最大也只用到 $\sqrt{x \times y}$ ，因为分析样例解释发现以后的都是重复的，只是换了个顺序而已，算 $2$ 遍即可。

优化 3： $a$ 可以从 $x$ 开始枚举，因为再小了最大公因数就没有 $x$ 了。

优化 4：每次可以加 $x$ ，因为余数有可加性， $x \equiv 0 (\bmod \hspace{0.1cm} x)$ ，所以能够保证最大公约数不低于 $x$ 。

优化 5： $x \ge 2$ ，所以 $a \ge y \div 2$ 时就不用枚举了。

结束~ ~~个 dir 啊~~

因为出事儿了……

下面这组数据阁下又该如何应对？

1
100 100

寄~

因为 $\sqrt{x * y}$ 的值若是整数按照刚才的逻辑会被算 $2$ 遍，然鹅换了个顺序还是这俩，不能重复计算啊！特判一下就得了……

ACCode：

1
// Problem: P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P1029
4
// Memory Limit: 125 MB
5
// Time Limit: 1000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<int, int> PII;
26

27
int x, y, ans;
28

29
template <typename T>
30

31
inline T read() {
32
  T sum = 0, fl = 1;
33
  char ch = getchar();
34
  for (; !isdigit(ch); ch = getchar())
35
    if (ch == '-') fl = -1;
36
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
37
  return sum * fl;
38
}
39

40
template <typename T>
41

42
inline void write(T x) {
43
  if (x < 0) {
44
    putchar('-'), write<T>(-x);
45
    return;
46
  }
47
  static T sta[35];
48
  int top = 0;
49
  do { sta[top++] = x % 10, x /= 10; } while (x);
50
  while (top) putchar(sta[--top] + 48);
51
}
52

53
int main() {
54
  x = read<int>(), y = read<int>();
55
  for (int i = x; i * i <= x * y && i < y >> 1; i += x)
56
    if (!(x * y % i) && gcd(i, x * y / i) == x) ans += 2;
57
  if (x == y) ans = 1;
58
  write<int>(ans);
59
  return 0;
60
}