c641 - 滿滿的糖果屋 #2

🔗 前往 ZeroJudge 原題

題目描述

題目描述了王老師帶了錢去糖果屋，購買不同單價糖果時會剩下不同的錢。已知三種糖果的單價分別為 3, 5, 7，剩餘的錢分別為 2, 3, 5。要求計算王老師最少帶了多少錢。

解題思路

題目可以轉化為求解同餘方程組：

• x ≡ 2 (mod 3)
• x ≡ 3 (mod 5)
• x ≡ 5 (mod 7)

其中 x 代表王老師帶的錢。由於數字範圍較小，可以直接使用暴力法，從最大的糖果單價開始，每次增加最小的糖果單價，直到滿足所有同餘條件。程式碼中 t 代表最小的糖果單價 (3)，a[0] 代表目前嘗試的錢的數量，a[1] 和 a[2] 分別代表 5 和 7。程式碼首先將 a[0] 增加到大於等於 max(a[1], a[2])，然後不斷增加 t，直到滿足所有同餘條件。

複雜度分析

• 時間複雜度: O(N)，其中 N 是答案的大小。因為程式碼使用暴力法，每次增加最小的糖果單價，直到找到滿足所有條件的答案。
• 空間複雜度: O(1)，程式碼只使用了固定大小的陣列來儲存糖果單價和剩餘的錢，空間複雜度為常數。

程式碼

#include <iostream>
using namespace std;
long long int a[3],b[3];
int main(){
	while(cin >> a[0] >> a[1] >> a[2] >> b[0] >> b[1] >> b[2]){
		long long int t=a[0];
		a[0]+=b[0];
		while(a[0]<max(a[1],a[2]))
			a[0]+=t;
		while(a[0]%a[1]!=b[1]||a[0]%a[2]!=b[2])
			a[0]+=t;
		cout << a[0] << '\n';
	}
}