f372 - 崑棋的臭豆腐
題目描述
題目要求計算臭豆腐炸 n 分鐘後的美味度。初始美味度為 1，每炸 1 分鐘美味度變成 3 倍。如果美味度超過 10006，則不斷減 10007 直到不超過 10006。題目要求輸出最終的美味度。
解題思路
這題的核心在於計算 3 的 n 次方模 10007 的值。直接計算 3 的 n 次方可能會導致整數溢出，因此需要使用快速冪 (Fast Power) 演算法。快速冪演算法通過將指數分解為二進制表示，並利用平方和乘法來有效地計算冪。此外，題目中提到如果美味度超過 10006，則需要減 10007，這實際上等同於取模 10007 的操作。因此，在計算快速冪的過程中，可以不斷地對中間結果取模 10007，以防止溢出並得到最終的結果。
複雜度分析
- 時間複雜度: O(log 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>
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[6],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline int mod(int p,int m){
if(p==0)return 1;
if(p==1)return 3;
bool o=p&1;
p>>=1;
int tmp=mod(p,m);
if(o)
return tmp*tmp*3%m;
else
return tmp*tmp%m;
}
int main(){
int n;
while(n=read()){
write(mod(n,10007));
putchar_unlocked('\n');
}
}