数论4——快速乘（1.0模板）

我就是我 2024-04-17 05:40 74阅读 0赞

##### 一、 普通乘法： #####

**对于a\*n**：  
普通乘法 本质： n个a相加；

/*******普通乘法*****/
    int ans;
    for(int i = 1;i <= n;i++)
    { 
    	ans+=a;
    }

普通乘法循环n次， 所以时间复杂度为O（n）， 如果n特别大， 普通乘法的效率就非常低。

##### 二、快速乘： #####

##### 1、我们一步一步的引入快速乘的原理。 #####

首先，加入你要算 a\*4； 用普通乘法要循环4次每次+a。

然而， 你有没有发现 在循环第二次时 t2 = a+a;  
我只需要再循环1次，将 ans = t2+t2;就能算出答案。 （如图）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]  
这样，就节省了一次循环。

是怎样节省了一次循环呢，上面我们演示的， 我们在算到 a*4 时，然后`利用了 a*2的结果`直接算出了a*4。  
快速乘就是基于这个原理， 利用之前计算的结果，提高了效率。

##### 2、快速乘讲解： #####

快速乘和快速幂都用到了二进制思想。

**对于a\*n**

假设n == 6吧：  
6的二进制为（110）  
那么 n就可以表示为（1\*22  +   1 \* 21  +  0 \* 20）

通过二进制转换的原理，现在该书被表示成了 就是指数函数 a \* 2b \* (0或1)的形式（x 为0 ， 1， 2…）。

所以我们可以模拟指数函数来计算 a×n的结果。  
当 二进制对应位为1时我们 就加上指数函数的这一项。  
为0就不加。

因为指数函数的 后一项 == 前一项的两倍（ Cn = Cn-1 \+Cn-1, n属于 1 ， 2 ， 3 ， 4 )的特点， 所以我们就可以利用指数函数的上一项计算下一项， 提高了计算效率。

ll quickmul(int a,int n,int mod)//快速乘
    { 
        ll ans=0;
        while(n)
        { 
            if(n&1)// n%2
                ans=(ans+a)%mod;
            a=(a+a)%mod;// 指数函数 (a×2^x == a× 2^x-1 + a× 2^x-1)
            n>>=1;// b/=2
        }
        return ans;
    }

##### 3、时间复杂度的证明 #####

[和快速幂相同——》][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzODI0Nzkx_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/86222169001242d69a447da516281fca.png
[Link 1]: https://blog.csdn.net/qq_43824791/article/details/89367438