e535 - 11344 - The Huge One
題目描述
題目要求判斷一個大數 M 是否能被給定的 1 到 12 之間的若干個數字整除。如果 M 能被所有給定的數字整除，則輸出 "M - Wonderful."，否則輸出 "M - Simple."。
解題思路
由於 M 是一個很大的數字，直接使用整數類型可能會溢出。因此，需要使用字串來表示 M，並使用模運算來判斷 M 是否能被給定的數字整除。
程式碼中，mod 函數計算字串表示的數字 M 對給定數字 a 的模。主函數讀取 M 和集合 S，然後遍歷集合 S 中的每個數字，如果 M 對任何一個數字的模不為 0，則判斷 M 不是 "Wonderful"，輸出 "M - Simple."。如果 M 對所有數字的模都為 0，則判斷 M 是 "Wonderful"，輸出 "M - Wonderful."。
程式碼首先移除 M 前導的 0，以避免不必要的計算。
複雜度分析
- 時間複雜度: O(N * L)，其中 N 是集合 S 的大小，L 是數字 M 的長度。
- 空間複雜度: O(L)，主要用於儲存數字 M 的字串表示。
程式碼
#include <iostream>
using namespace std;
int b,c,nl,it,bc;
string n;
inline int mod(string num, int a){
int res = 0;
for (int i = 0; i < nl; ++i)
res = (res*10 + (int)num[i] - '0') %a;
return res;
}
int main(){
cin >> c;
while(c--){
bool ans=0;
cin >> n >> bc;
string tmp;
nl=n.length();
for(it=0;it<nl-1;++it)
if(n[it]!='0')break;
for(;it<nl;++it)
tmp+=n[it];
while(bc--){
cin >> b;
if(ans==0&&mod(tmp,b)!=0)
ans=1;
}
if(ans)
cout << n << " - Simple.\n";
else
cout << n << " - Wonderful.\n";
}
}