因為有時候乘法會溢出，即使是long long也可能在乘法時爆掉。而使用快速乘會很高效完成乘法操作并且不會爆long long

快速乘就是將它轉化為加法，不是一個一個的加，仿照2進制加法操作來完成（快速乘需要它為正數，不能為負數）

O(1)的快速乘

typedef long double ld; typedef long long LL; typedef unsigned long long ull; LL ksc(LL x, LL y, LL p){LL z = (ld)x / p * y;LL res = (ull)x *y - (ull)z * p;return (res + p) % p; }

O(log)的快速乘

typedef long long LL; LL ksc(LL x, LL y, LL p){LL res = 0;while(y){if(y & 1) res = (res + x) % p;x = (x << 1) % p; //將x不斷乘2達到二進制y >>= 1;}return res; }

?

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的快速乘（模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。