c311 - PC:分組之塔

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算將一個大整數 n 除以 91 之後的餘數，因為塔主想要將部下以 91 人為單位分組，多出來的人數就是要被殺掉的。

解題思路

由於輸入的數字 n 可能非常大，直接使用整數類型會溢出。因此，需要將輸入的數字 n 轉換為字串，然後逐位讀取字串中的數字，並計算對 91 取模的結果。 每次讀取一位數字，將當前的餘數乘以 10，加上新的數字，然後再對 91 取模。 這樣可以避免數字過大而導致溢出。

複雜度分析

• 時間複雜度: O(N)，其中 N 是輸入字串的長度。
• 空間複雜度: O(1)，只需要常數級的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string a;
	while(cin >> a){
		int ans=0,al=a.length();
		for(int i=0;i<al;++i){
			ans*=10;
			ans+=a[i]-'0';
			ans%=91;
		}
		cout << ans << "\n";
	}
}