【递归乘法】【100%完美满分算法】【标准解法=快速乘】【反向优化=FFT】

本文主要是介绍【递归乘法】【100%完美满分算法】【标准解法=快速乘】【反向优化=FFT】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接
力扣题解链接

解题思路

少用乘法，到不用乘法

思路〇可以忽略, 就图一乐

• 思路〇：计算空间开销

1. 申请一个大小为\(a×b\)的数组
2. 计算其大小，并返回

class Solution {
public:
    int multiply(int A, int B) {
        bool a[A][B];
        return (int)sizeof(a);
    }
};

class Solution {
public:
    int multiply(int A, int B) {
        return (int)sizeof(bool[A][B]);
    }
};

• 思路一：\(FFT\)

1. 把两个数的系数表示通过\(FFT\)映射到点值表示，乘法的次数为\(O(Nlog(N))\)的数量级
2. 然后在点值表示下做乘法，乘法的次数为\(O(N)\)的数量级
3. 然后通过\(IDFT\)映射回系数表示，乘法的次数为\(O(Nlog(N))\)的数量级
4. 乘法总数：\(O(Nlog(N))\)

• 思路二：位运算

可以不用乘法吗？可以！

1. 我们可以把a×b看成十进制下的a×二进制下的b
2. 把b按照二进制下的位拆开来，于是就只要用加法代替乘法即可
3. 递归版本不优美，我是直接先写成了非递归式的，现在加上了递归版本（不能双百）
4. 乘法总数：\(O(0)\)

双百标准答案

class Solution {
public:
    int multiply(int A, int B) {
        int ans=0;
        for(long long a=max(A,B),b=min(A,B);b;b>>=1,a+=a)if(b&1)ans+=a;        
        return ans;
    }
};

class Solution {
public:
    void mul(int&ans,long long a,long long b){
        if(b==0)return;
        if(b&1)ans+=a;
        mul(ans,a+a,b>>1);
    }
    int multiply(int A, int B) {
        int ans=0;
        mul(ans,A,B);
        return ans;
    }
};

详细代码（有两份）

const int N = 1e6+10;
const double PI = acos(-1.0);

struct Complex {
	double r,i;
	Complex(double _r = 0,double _i = 0) {r = _r,i = _i;}
	Complex operator +(const Complex &b) {return Complex(r+b.r,i+b.i);}
	Complex operator -(const Complex &b) {return Complex(r-b.r,i-b.i);}
	Complex operator *(const Complex &b) {return Complex(r*b.r-i*b.i,r*b.i+i*b.r);}
};

void change(Complex* y,int len) {
	int i,j,k;
	for(i = 1, j = len/2; i < len-1; i++) {
		if(i < j)swap(y[i],y[j]);
		k = len/2;
		while( j >= k) {
			j -= k;
			k /= 2;
		}
		if(j < k)j += k;
	}
}

void fft(Complex* y,int len,int on) {
	change(y,len);
	for(int h = 2; h <= len; h <<= 1) {
		Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
		for(int j = 0; j < len; j += h) {
			Complex w(1,0);
			for(int k = j; k < j+h/2; k++) {
				Complex u = y[k];
				Complex t = w*y[k+h/2];
				y[k] = u+t;
				y[k+h/2] = u-t;
				w = w*wn;
			}
		}
	}
	if(on == -1) for(int i = 0; i < len; i++) y[i].r /= len;
}

Complex x1[N<<2];
Complex x2[N<<2];
int num[N<<1];

string mul(string s1,string s2) {
	int n=s1.size();
	int m=s2.size();
	int len=1;
	while(len < (n<<1) || len < (m<<1) ) len <<= 1;
	for(int i = 0; i < n; i++)	x1[i] = Complex(s1[i]-'0',0);
	for(int i = n; i < len; i++)x1[i] = Complex(0,0);
	for(int i = 0; i < m; i++)	x2[i] = Complex(s2[i]-'0',0);
	for(int i = m; i < len; i++)x2[i] = Complex(0,0);
	fft(x1,len,1);
	fft(x2,len,1);
	for(int i = 0; i < len; i++)x1[i] = x1[i]*x2[i];
	fft(x1,len,-1);
	for(int i = 0; i <n+m; i++)num[i] = (x1[i].r+0.5);
	for(int i=n+m-2; i>0; i--)num[i-1]+=num[i]/10,num[i]%=10;
	string res="";
	for(int i=0; i<n+m-1; i++)res+=to_string(num[i]);
	return res;
}

class Solution {
public:
    int multiply(int A, int B) {
        return atoi(mul(to_string(A),to_string(B)).c_str());
    }
};

class Solution {
public:
    int multiply(int A, int B) {
        int ans=0;
        long long a=max(A,B);
        long long b=min(A,B);
        while(b){
            if(b&1)ans+=a;
            b>>=1;
            a+=a;
        }
        return ans;
    }
};

这篇关于【递归乘法】【100%完美满分算法】【标准解法=快速乘】【反向优化=FFT】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！