f423 - 高雄市109年資訊競賽國中組第一題
題目描述
題目要求讀取一個正整數，將其乘以 2，然後計算平方值，最後除以 4。如果原始數字為奇數，則先將其加 1。最後將結果輸出。輸入以字元形式讀取，直到讀取到非數字字元為止。
解題思路
這題主要考驗對數字處理和數學運算的理解。程式碼首先讀取輸入字串，並將其轉換為整數。如果原始數字是奇數，則加 1。然後計算平方值，並除以 4。最後，將結果轉換為字串並輸出。核心邏輯是 a=(a<<3)+(a<<1)+c-'0'; 這行程式碼，它有效地將讀取的數字轉換為整數，並使用位移運算加速計算。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入數字的位數。主要時間花在讀取輸入和將結果轉換為字串上。
- 空間複雜度: O(1)，程式碼使用固定大小的陣列
stk來儲存數字的位數，因此空間複雜度是常數級別。
程式碼
#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>
int main(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
if(a&1)++a;
a=(a*a>>2);
int stk[9]={0},*ptr(&stk[0]);
while(a){*ptr=a%10;a/=10;++ptr;}
while(--ptr>=(&stk[0]))putchar_unlocked(*ptr+'0');
}