c640 - 滿滿的糖果屋 #1
題目描述
題目要求找出所有小於等於 M 且除以糖果單價後餘數為 k 的金額。糖果的單價會有多種，但數量不多（最多 4 種）。
解題思路
題目核心在於找出滿足 (金額 * v + k) <= M 的所有金額。程式首先讀取 M 和 k，以及糖果的單價。接著，計算所有糖果單價的最小公倍數 (LCM)。由於題目中提到單價為 3, 5, 7，因此可以先計算這些單價的 LCM。然後，程式迭代地計算 ans * v + k，其中 ans 是糖果單價的 LCM，v 是迭代變數。如果計算結果小於等於 M，則輸出該金額，並增加 v 的值。
程式碼中使用了 GCD (Greatest Common Divisor) 來簡化計算 LCM 的過程。在計算 LCM 時，先計算所有單價的乘積，然後除以它們之間的 GCD，以避免溢位。
複雜度分析
- 時間複雜度: O(N * M/LCM)，其中 N 是糖果種類的數量，M 是金額上限，LCM 是糖果單價的最小公倍數。由於 LCM 通常較小，且 N 的最大值為 4，因此時間複雜度可以近似為 O(M/LCM)。
- 空間複雜度: O(1)，程式只使用了固定大小的陣列來儲存糖果單價，因此空間複雜度為常數。
程式碼
#include <iostream>
using namespace std;
long long int m,k,a[6],it;
long long int gcd(long long int x,long long int y){
if( y==0 )
return x;
return gcd( y, x%y );
}
string s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> m >> k){
getline(cin,s);
getline(cin,s);
s+=' ';
it=0;
long long int tmp=0;
for(int i=0;i<s.length();++i){
if(s[i]>='0'&&s[i]<='9'){
tmp*=10;
tmp+=s[i]-'0';
}
else if(tmp!=0){
a[it]=tmp;
tmp=0;
++it;
}
}
long long int ans=a[0],v=1;
for(int i=1;i<it;++i){
if(gcd(ans,a[i])!=1)
a[i]/=gcd(ans,a[i]);
ans*=a[i];
}
while((ans*v+k)<=m){
cout << ans*v+k << " ";
++v;
}
cout << "\n";
}
}