e638 - 10176 - Ocean Deep! Make it shallow!!

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷一個大二進制數是否能被質數 131071 整除。輸入以 '#' 結尾，每個 '#' 處理完一組數字。

解題思路

這題的核心是處理大數的模運算。由於輸入的數字可能非常大，無法直接儲存在標準的整數類型中，因此需要逐位讀取數字，並在讀取的過程中進行模運算。程式碼使用 getchar_unlocked() 函數來快速讀取字符，並將二進制數字轉換為十進制數，同時對 131071 進行模運算。每次讀取一位二進制數字，就將當前結果乘以 2 (相當於左移一位)，然後加上讀取的數字，再對 131071 取模。

複雜度分析

• 時間複雜度: O(N)，其中 N 是輸入二進制數的長度。因為程式碼需要讀取並處理輸入的每一位。
• 空間複雜度: O(1)，程式碼只使用了常數個變數來儲存中間結果和狀態，不隨輸入大小變化。

程式碼

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
char a;
int main(){
	long long int ans=0;
	while(a=getchar_unlocked()){
		if(a==-1)break;
		if(a=='#'){
			if(!ans)
				puts("YES");
			else
				puts("NO");
			ans=0;
			continue;
		}
		ans=((ans+ans)+(a-48))%131071;
	}
}