ZeroJudge 解題筆記：f070. 1. 韓信點兵 (HanXin)

作者：王一哲
日期：2025年2月25日



ZeroJudge 題目連結：f070. 1. 韓信點兵 (HanXin)

解題想法

這題考數學，比較不像考演算法。

Python 程式碼

使用時間約為 25 ms，記憶體約為 3.3 MB，通過測試。

nums = sorted([list(map(int, input().split())) for _ in range(3)], reverse=True)
i = 1  # 倍數
while True:
    n = nums[0][0]*i + nums[0][1]  # 用最大的因數乘以 i 再加上餘數
    # 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
    if (n - nums[1][1])%nums[1][0] == 0 and (n - nums[2][1])%nums[2][0] == 0:
        print(n); break
    i += 1  # i 加 1

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<pair<int, int>> nums (3);
    for(int i=0; i<3; i++) cin >> nums[i].first >> nums[i].second;
    sort(nums.begin(), nums.end(), greater<pair<int, int>> ());
    int i = 1;  // 倍數
    while(true) {
        int n = nums[0].first*i + nums[0].second;  // 用最大的因數乘以 i 再加上餘數
        // 檢查 n 是否符合另外兩個因數，如果皆符合，印出 n 並中止迴圈
        if ((n - nums[1].second)%nums[1].first == 0 && (n - nums[2].second)%nums[2].first == 0) {
            cout << n << "\n"; break;
        }
        i++;  // i 加 1
    }
    return 0;
}