g183 - 81倍數判別

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷輸入的非負整數是否為 81 的倍數。如果輸入的數字是 81 的倍數，則輸出 "konopad!"，否則輸出 "konosuba!"。輸入數字可能很大，最長可達 100 位數。

解題思路

由於輸入數字可能很大，直接使用整數類型可能會溢出。因此，我們需要使用字符串來處理輸入，並逐步計算數字對 81 的餘數。 核心思想是利用模運算的性質：(a * 10 + b) % m = ((a % m) * 10 + b) % m。 我們從字符串的左邊開始，逐個字符地讀取數字，並更新當前的餘數。 每次讀取一個字符，將當前的餘數乘以 10，加上新的數字，然後對 81 取模。 最後，如果餘數為 0，則表示輸入的數字是 81 的倍數，否則不是。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字符串的長度。
• 空間複雜度: O(1)，因為我們只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string s;
	while(cin >> s){
		int tmp=0;
		for(int i=0;i<s.length();++i){
			tmp*=10;
			tmp+=s[i]-'0';
			tmp%=81;
		}
		if(tmp){
			cout << "konosuba!\n";
		}
		else{
			cout << "konopad!\n";
		}
	}
}