Sử dụng phép nhân ấn độ để tránh tràn số:
<a href="url">https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj</a>
<b>
Code mẫu:</b>
<pre class="language-cpp" tabindex="0">
<code class="language-cpp">long long mul(long long a, long long b){
if(b==1 or b==-1)
return (a*b)%MOD;
if(a==1 or a==-1)
return (a*b)%MOD;
long long temp = (a%MOD)*(b%2);
b /= 2;
long long x = mul(a,b);
return ((x + x)%MOD + temp ) % MOD;
}</code></pre>
Sử dụng [phép nhân Ấn Độ:](https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj)
$a \times b =$
$a \times \frac{b}{2} + a \times \frac{b}{2}$ (Nếu b là số chẵn)
$a \times \frac{b}{2} + a \times \frac{b}{2} + a$ (Nếu b là số lẻ)
## Code mẫu (dùng đệ quy):
<pre class="language-cpp" tabindex="0">
<code class="language-cpp">
long long mul(long long a, long long b){
if(b==1)
return a%MOD;
if(a==1)
return b%MOD;
long long temp = (a%MOD)*(b&1);
b /= 2;
long long x = mul(a,b);
return ((x + x)%MOD + temp) %MOD;
}
</code>
</pre>
## code mẫu (không dùng đệ quy):
<pre class="language-cpp" tabindex="0">
<code class="language-cpp">
long long mul(long long a, long long b){
long long res = 0;
a %= MOD;
while(b){
if(b & 1)
res = (res + a)%MOD;
a = (a<<1)%MOD;
//a = (a*2)%MOD
b >>= 1;
//b = b/2
}
return res;
}
</code>
</pre>
### Giải thích code không dùng đệ quy:
*Nếu b chẵn:*
Gấp đôi a và chia đôi b:
$a \times b = \left(2a\right) \times \frac{b}{2}$
*Nếu b lẻ:*
Vẫn gấp đôi a, chia đôi b nhưng cộng thêm a một lần:
$a \times b = \left(2a\right) \times \frac{b}{2} + a$
$\rightarrow$ **Tương tự phép nhân Ấn Độ ở trên**
vdgminh
Created at
3 likes
Im_stupid
Created at
0 likes