b430 - 簡單乘法
題目描述
題目要求計算 (a * b) % n 的值，其中 a、b 和 n 都是大整數（最大可達 10^18）。由於直接計算 a * b 可能會超出 64 位元的範圍，因此需要使用模運算的一些技巧來避免溢位。
解題思路
程式碼使用二進位乘法來計算 a * b % n。核心思想是將 b 轉換為二進位表示，然後根據 b 的每一位，將 a 乘以 2 的冪次，並累加結果，所有中間結果都進行模 n 運算，以防止溢位。mod 函數實現了這個二進位乘法和模運算。read 和 write 函數分別用於快速讀取和輸出 long long int 數值。
複雜度分析
- 時間複雜度: O(log b) (其中 b 是第二個輸入數，因為迴圈迭代次數與 b 的二進位表示的長度成正比)
- 空間複雜度: 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 long long int mod(long long int a,long long int b,long long int c){
long long int tmp=0;
for(;b;b>>=1,a<<=1,a=(a>=c)?a-c:a){
if(b&1){
tmp+=a;
if(tmp>=c)
tmp-=c;
}
}
return tmp;
}
inline void write(long long int x) {
if(x==0)putchar_unlocked('0');
long long int stk[20],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
int main(){
long long int a,b,c;
while(a=read(),b=read(),c=read()){
write(mod(a%c,b%c,c));
putchar_unlocked('\n');
}
}