d411 - 算了好久......
題目描述
題目要求判斷一個高達 9999 位的大數字 M 是否為 2 的 N 次方的倍數，其中 N 的範圍在 0 到 9 之間。如果 M 可以被 2 的 N 次方整除，則輸出 "YA!!終於算出M可被2的N次整除了!!"，否則輸出 "可惡!!算了這麼久M竟然無法被2的N次整除"。
解題思路
由於 M 是一個非常大的數字，直接使用標準的整數類型可能會溢出。因此，我們需要使用字串來表示 M，並模擬長除法的過程來計算 M 除以 2 的 N 次方的餘數。程式碼中 mod 函數實現了這個功能。它迭代字串中的每個數字，並逐步計算餘數。由於題目只需要判斷是否能整除，因此只需要計算餘數是否為 0 即可。
複雜度分析
- 時間複雜度: O(len(n))，其中 len(n) 是數字 M 的位數。因為
mod函數需要遍歷字串 n 的每一個字元。 - 空間複雜度: O(1)，因為程式碼使用的額外空間是常數級別的。
程式碼
#include <iostream>
using namespace std;
int b,ans;
string n;
inline int mod(string num, int a){
int res = 0;
for (int i = 0,nl = num.length(); i < nl; ++i)
res = (res*10 + (int)num[i] - '0') %a;
return res;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> b){
ans=mod(n,1<<b);
if(ans)
cout << "可惡!!算了這麼久" << n << "竟然無法被2的" << b << "次整除\n";
else
cout << "YA!!終於算出" << n << "可被2的" << b <<"次整除了!!\n";
}
}