2021牛客多校H-Hash Function[卷积]

本文主要是介绍2021牛客多校H-Hash Function[卷积]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Hash Function (https://ac.nowcoder.com/acm/contest/11166/H)

题意：
对于给定的集合\(S=\{a_0,a_1,...,a_{n-1}\}\)，找到最小的正整数\(x\)，使得所有数对\(x\)取模的结果互不相同。
其中 \(1 \le n \le 500000, 0 \le a_i \le 5000000, a_i \ne a_j\)

解法：
事后诸葛亮，这题做法是卷积。

求出\(a_i\)之间的差都有哪些，然后这些差的因数都不能是x。筛掉这些因数后最小数就是\(x\)。

如何筛掉差的因数呢？可以看出\(a_i\)的范围不大，先枚举因数\(i\)，再枚举倍数\(k\)即可，时间复杂度\(O(n/1+n/2+...+n/n)=O(nlogn)\)

如何求出所有差值呢？卷积。\(\{a_0,a_1,...,a_{n-1}\}\)和\(\{a_{1-n},a_{2-n},...,a_0\}\)用01序列表示（比如说，vis[i]=0集合中没有i，vis[i]=1表示集合中有i），求fft加速的卷积即可求出\(b_k=\sum_{i=0}^{n-1}a_i\times a_{k-i}\)，时间复杂度\(O(nlogn)\)

这是我第一次写fft和卷积，因此留下模板供以后使用：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=500000;
const double Pi=acos(-1);

//fft complex struct
struct Complex{
	double x, y;
	Complex(double x=0, double y=0):x(x),y(y){}
	Complex operator+(Complex b){ return Complex(x+b.x,y+b.y); }
	Complex operator-(Complex b){ return Complex(x-b.x,y-b.y); }
	Complex operator*(Complex b){ return Complex(x*b.x-y*b.y,x*b.y+y*b.x); }
};

//fft varity define
int n, m;
Complex a[N+10<<2], b[N+10<<2], c[N+10<<2];
int r[N+10<<2];

//fft by butterfly
void fft(Complex *cm, LL cnum, LL tag){
	for(int i=0; i<cnum; ++i) if(i<r[i]) swap(cm[i],cm[r[i]]);
	for(int mid=1; mid<cnum; mid<<=1){
		Complex wk=Complex(cos(2*Pi/(2*mid)),tag*sin(2*Pi/(2*mid)));
		for(int j=0; j<cnum; j+=2*mid){
			Complex w(1,0);
			for(int k=0; k<mid; ++k){
				Complex buf=w*cm[j+k+mid];
				cm[j+k+mid]=cm[j+k]-buf;
				cm[j+k]=cm[j+k]+buf;
				w=w*wk;
			}
		}
	}
}

//problem
int an;
bool vis[N+N+20];

int main(){
	cin>>an;
	for(int i=1, u; i<=an; ++i){
		scanf("%d", &u);
		a[u].x=1;
		b[N-u].x=1;
	}
	
	//fft butterfly generation
	int dgt=1, bits=0;
	while(dgt<=N+N) { dgt<<=1; bits++; }
	for(int i=0; i<dgt; ++i) r[i]=(r[i>>1]>>1)|((i&1)<<(bits-1));
	//fft
	fft(a,dgt,1);
	fft(b,dgt,1);
	for(int i=0; i<=dgt; ++i){
		c[i]=a[i]*b[i];
	}
	fft(c,dgt,-1);
	//problem
	for(int i=0; i<=N+N; ++i){
		vis[i]=((int)(c[i].x/dgt+0.5))!=0;
	}
	for(int i=N; i<=N+N; ++i){
		vis[i]|=vis[N+N-i];
	}
	for(int i=0; i<=N; ++i){
		vis[i]=vis[i+N];
	}
	vis[N+1]=false;
	for(int i=1; i<=N+1; ++i){
		bool ok=true;
		for(int j=i; j<=N+1&&ok; j+=i){
			if(vis[j]) ok=false;
		}
		if(ok){
			printf("%d\n", i);
			break;
		}
	}
	return 0;
}

这篇关于2021牛客多校H-Hash Function[卷积]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！