若两个数(n,m)相乘,不允许使用(*)运算符.
我们发现(n*m)的性质类似于快速幂(n^m)的性质,故可以使用快速幂加速。`
int n_mul_m(int n, int m)
{
int ans = 0;
while(m)
{
if(m&1) ans += n;
n += n;
m >>= 1;
}
return ans;
}
我们发现(n*m)的性质类似于快速幂(n^m)的性质,故可以使用快速幂加速。`
int n_mul_m(int n, int m)
{
int ans = 0;
while(m)
{
if(m&1) ans += n;
n += n;
m >>= 1;
}
return ans;
}