题目描述：?小花有一个数组A，小树有一个数组B。小花和小树的关系很好，他们希望合并手中的数组，得到新的集合C={a+b|a∈A, b∈B}。
输入格式：第一行输入两个整数N,M，分别表示数组A,B的长度。第二行包含N个整数，表示数组A。第三行包含M个整数，表示数组B。
? (0 ≤ N,M ≤ 2 *10^5, 0 ≤ A[i],B[i] ≤ 2 * 10^6)
输出格式：输出一个整数，表示C的元素个数。
输入样例：
10 10
12 14 0 2 2 15 26 17 8 44
1 4 6 10 22 13 19 50 39 0
输出样例：
56
注意：本题时间限制较严格，由于暴力解法时间复杂度为O(n^2)，可能无法满足本题要求，因此请尽可能优化你的算法（ 6000ms，512MB）。
分析：我们首先想到的算法就是暴力解法，用双重循环实现。源程序如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
int n, m;
scanf("%d %d", &n, &m);
int* arrl=(int*)malloc(sizeof(int) * n);
int* arr2=(int*)malloc(sizeof(int) * n);
if (arrl==NULL || arr2 == NULL) return 1;
for (int i = 0; i < n; ++i) {
scanf("%d",&arrl[i]);
}
for(int i = 0; i< m; ++i) {
scanf("%d",&arr2[i]);
}
char* check =(char*)malloc(sizeof(char) * 4000001);
if (check == NULL) return 1;
memset (check, 0, sizeof(char) * 4000001);
int count= 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
check[arrl[i] + arr2[j]]=1;
}
}
for(int i=0; i< 4000001; i++){
count += check[i];
}
printf("%d\n",count);
return 0;
}暴力算法虽然简单，但数据量大时，运行时间会超时，因为算法的时间复杂度为O(n^2)，无法满足题目要求。因此，必须找到一种解决方案。因此有网友提出一种方案，使用傅里叶变换实现。
设A数组[0, 1, 3, 5, 6]中的元素可看成多项式（1+x+x^3+x^5+x^6)的系数，B数组中[2,3,4]中的元素可看成多项式(x^2+x^3+x^4)的系数。计算这两个多项式的乘法（1+x+x^3+x^5+x^6)*(x^2+x^3+x^4)，然后看结果中哪些项前面有系数，统计有系数项的个数，即为所求答案。
使用快速傅里叶变换进行多项式乘法运算，其时间复杂度为O（nlogn)，应能满足题目要求。源程序如下。
#include <stdio.h>
#define LLONG long long
#define MAXN (1<<23)
#define mod 998244353 //质数,在编程中常被用来做模数
int id[MAXN];
int a[ MAXN],b[ MAXN];
int quickpow(int x, int b)
{
LLONG ans=1,t=x;
while(b){
if(b&1) ans=ans*t%mod;
t=t*t%mod;
b>>=1;
}
return ans;
}
int init(int len)
{
int lim=1;
while(lim<=len) {
lim<<=1;
}
for(int i=1; i<lim; i++){
id[i] = (id[i>>1]>>1)+(i&1)*(lim>>1);
}
return lim;
}
void NTT(int a[],int lim, int opt)
{
for(int i=1; i<lim; i++){
if(i<id[i]) {
int step = a[i];
a[i] = a[id[i]];
a[id[i]] = step;
}
}
for(int len=2; len<=lim; len<<=1) {
int k=len>>1;
int wn=quickpow(3,(mod-1)/len);
for(int i=0; i<lim; i+=len){
LLONG g=1;
for(int j=0; j<k; j++,g=g*wn%mod){
int temp=a[i+j+k]*g%mod;
a[i+j+k]=(mod-temp+a[i+j])%mod;
a[i+j]=(a[i+j]+temp)%mod;
}
}
}
if(opt==-1) {
for (int i = 0; i < lim; i++){
int temp = a[i+1];
a[i+1] = a[lim - i];
a[lim - i] = temp;
}
LLONG inv=quickpow(lim,mod-2);
for(int i=0; i<lim; i++) {
a[i]=a[i]*inv%mod;
}
}
return;
}
int main()
{
int n,m,lim=0;
int x,i;
scanf("%d%d",&n,&m);
for(i=1; i<=n; i++) {
scanf("%d",&x);
a[x]=1;
if(x>lim)lim=x;
}
for(i=1; i<=m; i++) {
scanf("%d",&x);
b[x]=1;
if(x>lim)lim=x;
}
lim = init(lim<<1);
NTT(a,lim,1);
NTT(b,lim,1);
LLONG step;
for(i=0; i<lim; i++){
step = a[i];
a[i]=step*b[i]%mod;
}
NTT(a,lim,-1);
for(i=0,n=0; i<lim; i++) {
if(a[i]) n++;
}
printf("%d",n);
return 0;
}参考文献：
[1]https://tieba.baidu.com/p/8844914020
[2]百度网盘资源下载网址
https://pan.baidu.com/s/17ZXphwqySNIsIgcGtYMjvg?pwd=lhwc
[3]李红卫，李秉璋.?C程序设计与训练（第四版）[M]，大连，大连理工大学出版社，2023.