[牛客多校]第一场H.Hash Function

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

题意：定义哈希函数\(h_{seed}(x) = x \mod{seed}\)，给定一个集合，要求找到一个最小的\(seed\)，使得集合内的数字哈希函数两两不同。
数据范围：\(n\le 5\times 10^5, a_i\le 5\times 10^5\)

注意到两个数字的哈希函数当且仅当$seed | (a_i - a_j) \(，假如我们知道每一个\)(a_i -a _j)\(是否存在，我们枚举每个\)seed\(，然后判断\)seed\(的每个倍数是否存在，这个过程是\)O(nlogn)$的，因为调和级数。

于是问题变成怎么快速求出每个\((a_i - a_j)\)是否存在。

\(f(i)\)表示\(i\)是否存在，反转整个数组，变成\(g(x) = f(500000 - x)\)，然后跟原数组卷积，我们发现卷积\(h(x) = \sum f(i) * f(50000 - x - i)\)，\(f(i),f(50000 - x - i)\)都不为\(0\)的时候对数组有贡献，表示存在这样的一个\((a_i - a_j)\)。

于是NTT随便卷一下就行了。

#include <bits/stdc++.h>
#define pt(x) cout << x << endl;
#define Mid ((l + r) / 2)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read() {
	char c; int num, f = 1;
	while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
	while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
	return f * num;
}
const int P = 998244353, G = 3, Gi = 332748118;
const int N = 5e5, M = N * 5 + 1009;
int n, A[M], B[M];
int Pow(int a, int p) {
	int ans = 1;
	for( ; p; p >>= 1, a = 1ll * a * a % P)
		if(p & 1)
			ans = 1ll * a * ans % P;
	return ans % P;
}
namespace Polynomial {
	const double Pi = acos(-1.0);
	int rev[M];
	template <typename T>
	void change(T *y, int n) {
		for(int i = 0; i < n; i++) 
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
		for(int i = 0; i < n; i++) 
			if(i < rev[i])
				swap(y[i], y[rev[i]]);
	}
	void NTT(int *A, int n, int type) {
		//type = 1 DFT 
		//type = -1 IDFT 
		change(A, n);
		for(int m = 1; m < n; m <<= 1) {
			int Wn = Pow(type == 1 ? G : Gi, (P - 1) / (m << 1));
			for(int i = 0; i < n; i += 2 * m) {
				int w = 1;
				for(int j = 0; j < m; j++, w = 1ll * w * Wn % P) {
					int x = A[i + j], y = 1ll * w * A[i + j + m] % P;
					A[i + j] = (x + y) % P;
					A[i + j + m] = (x - y + P) % P;
				} 
			}
		}
		if(type == -1) {
			int inv = Pow(n, P - 2);
			for(int i = 0; i < n; i++)
				A[i] = 1ll * A[i] * inv % P;
		}
	}
	
}
int check(int x) {
	for(int i = x; i <= N; i += x) 
		if(A[i]) 
			return false;
	return true;
}
signed main()
{
	n = read();
	for(int i = 1; i <= n; i++) {
		int x = read();
		A[x] = 1;
		B[N - x] = 1;
	}
	int lim = 1;
	while(lim <= 2 * N) lim <<= 1;
	Polynomial :: NTT(A, lim, 1); 
	Polynomial :: NTT(B, lim, 1);
	for(int i = 0; i < lim; i++) A[i] = 1ll * A[i] * B[i] % P;
	Polynomial :: NTT(A, lim, -1); 
	reverse(A, A + 1 + N);
	int i = n;
	while(1) {
		if(check(i)) {
			printf("%d\n", i);
			return 0;
		}
		i++;
	}
	return 0;
}

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