week1-[分支嵌套]公因数

week1-[分支嵌套]公因数

题目描述

给定 $4$ 个正整数 $a,b,c,k$。如果 $a,b,c$ 都是 $k$ 的倍数，那么称 $k$ 是 $a,b,c$ 的公因数。否则如果某两个数都是 $k$ 的倍数，那么称 $k$ 是这两个数的公因数。问 $k$ 是哪些数的公因数？

输入格式

输入共 $1$ 行 $4$ 个正整数 $a,b,c,k$。

输出格式

输入共 $1$ 行，为 ab 或 ac 或 bc 或 abc 表示答案。如果 $k$ 不是某两个数或这三个数的公因数，输出 none。

样例 #1

样例输入 #1

8 10 14 2

样例输出 #1

abc

样例 #2

样例输入 #2

11 16 15 5

样例输出 #2

none

样例 #3

样例输入 #3

9 16 12 3

样例输出 #3

ac

提示

数据范围

对于所有数据，$1\le a,b,c,k\le 1000$。

week1-[分支嵌套]公因数 题解

1. 阅读题目

给定 4 个正整数 a,b,c,ka,b,c,ka,b,c,k，我们要判断 kkk 是否为 a,b,ca,b,ca,b,c 的公因数。

规则：

• 如果 a、b、c 都是 kkk 的倍数 → 输出 abc
• 否则，如果有且只有两个是 kkk 的倍数 → 输出对应的两个字母（ab / ac / bc）
• 如果没有两个或三个数是 kkk 的倍数 → 输出 none

---

2. 分析问题

• 判断是否是倍数：用 x % k == 0。
• 优先级：
  1. 三个数都满足 → abc
  2. 只满足两个数 → 输出这两个字母
  3. 其他情况 → none
• 因为三个数的判断优先，所以可以用 分支嵌套 先判断三人情况，再判断两人情况。

---

3. 解决方案

• 读入 a, b, c, k

• 判断：

  if (a%k==0 && b%k==0 && c%k==0) 输出 "abc"
  else if (a%k==0 && b%k==0) 输出 "ab"
  else if (a%k==0 && c%k==0) 输出 "ac"
  else if (b%k==0 && c%k==0) 输出 "bc"
  else 输出 "none"
  

---

4. C++ 代码实现

#include <iostream>
using namespace std;int main() {int a, b, c, k;cin >> a >> b >> c >> k;if (a % k == 0 && b % k == 0 && c % k == 0) {cout << "abc";} else if (a % k == 0 && b % k == 0) {cout << "ab";} else if (a % k == 0 && c % k == 0) {cout << "ac";} else if (b % k == 0 && c % k == 0) {cout << "bc";} else {cout << "none";}return 0;
}

---

5. 数据测试

样例 1

输入

8 10 14 2

过程

• 8 % 2 == 0
• 10 % 2 == 0
• 14 % 2 == 0
  → 三个都满足 → 输出 abc

输出

abc

---

样例 2

输入

11 16 15 5

过程

• 11 % 5 != 0
• 16 % 5 != 0
• 15 % 5 == 0
  → 只有一个满足 → 输出 none

输出

none

---

样例 3

输入

9 16 12 3

过程

• 9 % 3 == 0
• 16 % 3 != 0
• 12 % 3 == 0
  → 满足 a 和 c → 输出 ac

输出

ac

---

6. 时间复杂度与空间复杂度

• 时间复杂度：常数级 O(1)
• 空间复杂度：常数级 O(1)

---

7. 优化方案

• 目前是固定 3 个数，如果扩展到更多数，可以用数组存储，然后统计 %k==0 的元素下标，输出对应标签。
• 如果数据很大，可提前判断 k 是否大于最大值，直接输出 none，减少取模运算次数（本题数据量极小，这种优化无意义）。