🥇 Taiwan

TOI 臺灣國際資訊奧林匹亞競賽 Taiwan Olympiad in Informatics 📅 2024/09/30~2024/10/04 🧒 新手組 T3

因數計算 (Factor)

📝 問題敘述

在數學中，若自然數 a 可以被自然數 b 整除，則我們稱 b 為 a 的因數。1 是所有正整數的因數；所有正整數，也是自己的因數。

現在給定一區間 x 到 y，求區間內（含 x 和 y）擁有最多因數的正整數 N 及其因數個數 M；若有多個 N，請給出較小的數。

📥 輸入格式

• 輸入含有兩個正整數 x 和 y (1 ≤ x < y ≤ 10^5，y - x < 10^3)。

📤 輸出格式

• 輸出兩個正整數 N 和 M，N 表示區間內含有最多因數的正整數，M 表示因數個數；
• 若區間內有多個符合條件的 N，請輸出最小的。

📚 範例 1

輸入：

13 19

輸出：

18 6

📚 範例 2

輸入：

1 3

輸出：

2 2

💡 評分說明

此題目測資分為兩組，每組測資有多筆測試資料，需答對該組所有測資才能獲得該組分數。各組詳細限制如下：

1. ​**第一組 (20 分)**​：0 < x < y < 10。
2. ​**第二組 (80 分)**​：無特別限制。

💡 思路說明

1. ​因數計算​：對於區間內的每一個數字，計算其因數的個數。
   • 計算因數的方式是對每個數字進行循環檢查其所有的整數除數，直至該數字的平方根。
2. ​比較最大因數個數​：找出區間內因數最多的數字 N，並記錄其因數個數 M。如果有多個數字擁有相同的最大因數個數，選擇最小的數字 N。

🎯 解題步驟

1. ​**遍歷區間 [x, y]**​：對每個數字計算其因數個數。
2. ​更新最大因數個數​：每當找到新的因數最多的數字時，更新 N 和 M。
3. ​輸出結果​：最後輸出擁有最多因數的數字 N 和其因數個數 M。