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，減少取模運算次數（本題數據量極小，這種優化無意義）。