a538 - 11879 - Multiple of 17

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個正整數 n，要求判斷 n 是否為 17 的倍數。題目提供了一個判斷 17 倍數的定理：若且唯若，移除 n 的最後一個位數 d，其值再減去 5d 之後，若為 17 的倍數，則 n 亦為 17 的倍數。

解題思路

題目提供了一個簡化的判斷 17 倍數的方法。程式碼直接利用這個定理，透過模數運算來判斷。由於輸入的數字可能較大，直接使用字串輸入，並在迴圈中逐步計算模數。mod 函數計算字串表示的數字對 17 的模數。在主函數中，讀取字串形式的數字，如果數字為 0，則結束迴圈。否則，呼叫 mod 函數計算模數，如果模數為 0，則輸出 1，否則輸出 0。

複雜度分析

• 時間複雜度: O(N)，其中 N 是輸入數字的位數。因為 mod 函數需要遍歷輸入字串的每個字符。
• 空間複雜度: O(1)，程式碼使用的額外空間是常數級別。

程式碼

#include <iostream>
using namespace std;
int b;
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(){
	while(cin >> n){
		if(n=="0")break;
		cout << !mod(n,17) << "\n";
	}
}