jerry3128

用户名：jerry3128

访问量：3136

签　名：

等　　级
排　　名	18011
经　　验	757
参赛次数	3
文章发表	3
年　　龄	0
在职情况	学生
学　　校	晃华媛中学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-高精度乘法（C++代码）----> (FFT)
浏览：1255

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

蓝桥杯算法提高VIP-高精度乘法（C++代码）----> (FFT)

　　作者: jerry3128　　　　发表时间：2019-12-07 11:53:04 浏览：1255　|　评论：0　

原题链接：蓝桥杯算法提高VIP-高精度乘法

FFT（Fast Fourier Transformation），中文名快速傅里叶变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
朴素高精度乘法的时间为O(n^2)，但FFT只需O(nlog^2n)
核心在于系数与点值的转换。
接下来就是模板了。
最好手写complex...
```
#include<bits/stdc++.h>
#define Pi (acos(-1.0))
using namespace std;
int getint() {
	char ch=getchar();
	int ret=0,flag=1;
	while(ch<'0'||ch>'9') {
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		ret=(ret<<3)+(ret<<1)+ch-'0';
		ch=getchar();
	}
	return ret*flag;
}
struct Complex {
	double real,imag;
	Complex operator +(Complex b) {
		Complex ret;
		ret.real=real+b.real;
		ret.imag=imag+b.imag;
		return ret;
	}
	Complex operator -(Complex b) {
		Complex ret;
		ret.real=real-b.real;
		ret.imag=imag-b.imag;
		return ret;
	}
	Complex operator *(Complex b) {
		Complex ret;
		ret.real=real*b.real-imag*b.imag;
		ret.imag=real*b.imag+b.real*imag;
		return ret;
	}
} wi[4000005];
int rev[4000005];
int pre(int x) {
	int l=ceil(log2(x)),len=1<<l;
	for(int i=1; i<len; i++)rev[i]=rev[i>>1]>>1|((i&1)<<(l-1));
	return len;
}
void FFT(Complex A[],int len,int f) {
	for(int i=0; i<len; i++)if(rev[i]<i)swap(A[i],A[rev[i]]);
	for(int i=1; i<len; i<<=1) {
		Complex wn= {cos(1.0*f*Pi/i),sin(1.0*f*Pi/i)};
		wi[0]= {1,0};
		for(int j=1; j<i; j++)wi[j]=wi[j-1]*wn;
		for(int j=0; j<len; j+=i<<1) {
			for(int k=0; k<i; k++) {
				Complex x=A[j+k],y=A[j+k+i]*wi[k];
				A[j+k]=x+y;
				A[j+k+i]=x-y;
			}
		}
	}
	if(f==-1)for(int i=0; i<len; i++)A[i].real=A[i].real/len;
}
int n,sum[4000005],tot;
Complex a[4000005],b[4000005];
char c[4000005];
int main() {
//	n=getint();
//	n=pre(n<<1);
	scanf("%s",c+1);
	n=strlen(c+1);
	for(int i=0; i<strlen(c+1); i++)a[i].real=c[strlen(c+1)-i]^48;
	scanf("%s",c+1);
	n=n>strlen(c+1)?n:strlen(c+1);
	for(int i=0; i<strlen(c+1); i++)b[i].real=c[strlen(c+1)-i]^48;
	n=pre(n<<1);
	FFT(a,n,1);
	FFT(b,n,1);
	for(int i=0; i<n; i++) {
		a[i]=a[i]*b[i];
	}
	FFT(a,n,-1);
	for(int i=0; i<n; i++) {
		sum[i]+=(a[i].real+0.5);
		sum[i+1]+=sum[i]/10;
		sum[i]%=10;
	}
	int l=n;
	while(!sum[l])l--;
	while(l>=0)putchar(sum[l--]^48);
	putchar('\n');
	return 0;
}
```

0.0分

12 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

2^k进制数（C++代码）使用递归方法

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-统计字符（C语言代码）

jerry3128

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

C二级辅导-等差数列（C语言代码）

点我有惊喜！你懂得！

蓝桥杯算法提高VIP-高精度乘法（C++代码）----> (FFT)

评论区

精彩推荐

2^k进制数（C++代码）使用递归方法

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-统计字符（C语言代码）

jerry3128

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （Java代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

C二级辅导-等差数列 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯算法提高VIP-高精度乘法 （C++代码）----> (FFT)

评论区

精彩推荐

2^k进制数 （C++代码）使用递归方法

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-统计字符 （C语言代码）

用筛法求之N内的素数。（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

C二级辅导-等差数列（C语言代码）

蓝桥杯算法提高VIP-高精度乘法（C++代码）----> (FFT)

　　评论区

2^k进制数（C++代码）使用递归方法

C二级辅导-统计字符（C语言代码）