✅ 魔法学徒的双重身份

🌟 题目背景

在魔法王国，学院里共有 nn 名魔法学徒，每个学徒都有自己的编号$1,2,\dots,n。$

• 有 A 名学徒加入了 ​火系小组​。
• 有 B 名学徒加入了 ​水系小组​。
• 有 C 名学徒同时加入了 ​火系和水系小组​。

学院统计部门想知道： ​至少加入一种小组的学徒中，有多少对学徒 (x,y) 满足 $\gcd(x,y) = 1$​？ （这里一对学徒 (x,y) 要求x<y，不计顺序。）

---

📥 输入格式

n A B C

• n：学徒总数，编号 1 到 n
• A：火系小组人数
• B：水系小组人数
• C：同时加入火系和水系的人数

---

📤 输出格式

X
Y

• 第一行：X = 至少加入一种小组的学徒数

$X = A + B - C$

• 第二行：Y = 在这 X 名学徒中，所有编号两两组合中 $\gcd(x,y)=1$ 的 ​组合对数​。

---

📋 输入样例

10 6 5 2

步骤解析：

1. 容斥原理：

$X = A + B - C = 6 + 5 - 2 = 9→$ 考虑编号 1 到 9 的学徒。

2. 枚举所有对 (x,y)：

$1 \le x < y \le 9$统计$\gcd(x,y)=1$。

• 例如 (1,2)、(1,3)、(1,4)…都满足
• (2,4) 不满足（gcd=2）

输出结果：

9
<程序计算出的对数>

---

✨ 思路

✔ 第一步：容斥

$X = A + B - C$ ✔ 第二步：在集合 {1,2,…,X} 中，统计满足 gcd(x,y)=1 的二元组对数。

---

📌 数据范围

为避免暴力超时，建议：

$1 \leq X \leq 2000$（若 X 更大，可用数论方法或预处理筛选优化）

---

🎯 知识点融合

✔ ​容斥原理​：计算至少在一个集合中的人数 ✔ ​最大公约数 GCD​：检查编号是否互质 ✔ ​双重枚举​：统计符合条件的对数

---