Hash Function

求出满足$a_i\%mod\ne a_j\%moda\_i\backslash \%mod\backslash neq\; a\_j\backslash \%mod$ai​%mod​=aj​%mod的最小的$mod\{mod\}$mod

之前在百度之星写过类似的题萌新，但是哪一题是求满足$a_i\%mod=a_j\%moda\_i\backslash \%mod=\; a\_j\backslash \%mod$ai​%mod=aj​%mod的最小的$mod\{mod\}$mod。

当时拿着这道题（假设$a_i>a_{j}a\_i>a\_j$ai​>aj​，且下面的除法都向下取整），当$a_i\ne a_{j}a\_i\backslash neq\; a\_j$ai​​=aj​时，习惯性拆成

$a_i-\frac{a_i}{mod}mod=a_j-\frac{a_j}{mod}\ast moda\_i-\backslash frac\{a\_i\}\{mod\}mod=a\_j-\backslash frac\{a\_j\}\{mod\}*mod$ai​−modai​​mod=aj​−modaj​​∗mod

$a_i-a_j=\frac{a_i}{mod}mod-\frac{a_j}{mod}\ast moda\_i-a\_j=\backslash frac\{a\_i\}\{mod\}mod-\backslash frac\{a\_j\}\{mod\}*mod$ai​−aj​=modai​​mod−modaj​​∗mod

$a_i-a_j=(\frac{a_i}{mod}-\frac{a_j}{mod})\ast moda\_i-a\_j=(\backslash frac\{a\_i\}\{mod\}-\backslash frac\{a\_j\}\{mod\})*mod$ai​−aj​=(modai​​−modaj​​)∗mod

则$mod\mid (a_i-a_j)mod|(a\_i-a\_j)$mod∣(ai​−aj​)，于是有：

$a_i-a_j=(\frac{a_i-a_j+a_j}{mod}-\frac{a_j}{mod})\ast moda\_i-a\_j=(\backslash frac\{a\_i-a\_j+a\_j\}\{mod\}-\backslash frac\{a\_j\}\{mod\})*mod$ai​−aj​=(modai​−aj​+aj​​−modaj​​)∗mod

$a_i-a_j=(\frac{a_i-a_j}{mod}+\frac{a_j}{mod}-\frac{a_j}{mod})\ast moda\_i-a\_j=(\backslash frac\{a\_i-a\_j\}\{mod\}+\backslash frac\{a\_j\}\{mod\}-\backslash frac\{a\_j\}\{mod\})*mod$ai​−aj​=(modai​−aj​​+modaj​​−modaj​​)∗mod，因为$mod\mid (a_i-a_j)mod|(a\_i-a\_j)$mod∣(ai​−aj​)，所以可以把分数拆开

$a_i-a_j=\left(\frac{a_i-a_j}{mod}\right)\ast moda\_i-a\_j=(\backslash frac\{a\_i-a\_j\}\{mod\})*mod$ai​−aj​=(modai​−aj​​)∗mod

所以我们可以发现所有的$mod\mid (a_i-a_j)mod|(a\_i-a\_j)$mod∣(ai​−aj​)都满足$a_i\%mod=a_j\%moda\_i\backslash \%mod=\; a\_j\backslash \%mod$ai​%mod=aj​%mod，于是最小的模数就是$a_i-a_{j}a\_i-a\_j$ai​−aj​的最小质因子，最大的模数就是$a_i-a_{j}a\_i-a\_j$ai​−aj​。特判$a_i-a_j==1a\_i-a\_j==1$ai​−aj​==1的情况，无解。

当$a_i==a_{j}a\_i==a\_j$ai​==aj​时，$2\sim a_{i}2\backslash sim\; a\_i$2∼ai​都是满足条件的余数。特判$a_i==a_j==1a\_i==a\_j==1$ai​==aj​==1的情况，无解。

回到这一题，更好的证法：

$a_i\%mod\ne a_j\%moda\_i\backslash \%mod\backslash neq\; a\_j\backslash \%mod$ai​%mod​=aj​%mod

$a_j\%mod=(a_i+a_j-a_i)\%moda\_j\backslash \%mod=(a\_i+a\_j-a\_i)\backslash \%mod$aj​%mod=(ai​+aj​−ai​)%mod

所以$\mid a_i-a_j\mid \%mod\ne 0|a\_i-a\_j|\backslash \%mod\backslash neq\; 0$∣ai​−aj​∣%mod​=0

所以这一题的模数不能是任何一个$\mid a_i-a_j\mid |a\_i-a\_j|$∣ai​−aj​∣的因子。

朴素的找出所有的$\mid a_i-a_j\mid |a\_i-a\_j|$∣ai​−aj​∣复杂度就是$O\left(n^2\right)O(n^2)$O(n2)。

对于集合$A=a_0+a_1+...+a_n,B=b_0+b_1+...+b_{m}A=a\_0+a\_1+...+a\_n,B=b\_0+b\_1+...+b\_m$A=a0​+a1​+...+an​,B=b0​+b1​+...+bm​，求集合$C=\{c_k,c_k=a_i-b_j\}C=\backslash \{c\_k,c\_k=a\_i-b\_j\backslash \}$C={ck​,ck​=ai​−bj​}

这个可以用$NTTNTT$NTT去做。假设集合A中存在的元素$valval$val，那么集合A对应的多项式某一项为$1\ast x^{val}1*x^\{val\}$1∗xval；假设集合B中存在的元素$disdis$dis，那么集合A对应的多项式某一项为$1\ast x^{P-dis}1*x^\{P-dis\}$1∗xP−dis。两个多项式相乘后得到$1\ast x^{val+P-dis}1*x^\{val+P-dis\}$1∗xval+P−dis，于是得到$val-disval-dis$val−dis。

可以知道的是$\mid a_i-a_j\mid |a\_i-a\_j|$∣ai​−aj​∣不超过$2\ast N2*N$2∗N个，而每个数不超过$N=5e5N=5e5$N=5e5，所以可以先NTT求出所有的差的绝对值并标记，然后从$nn$n开始枚举模数，调和级数来判断模数是否满足条件。

NTT代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=(1<<20)+7,p=5e5,mod=998244353;
inline int qpow(int x,int y) {
	int res(1);
	while(y) {
		if(y&1) res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int r[maxn];
inline void ntt(int *x,int lim,int opt) {
	int i,j,k,m,gn,g,tmp;
	for(i=0;i<lim;++i) 
		if(i<r[i]) swap(x[i],x[r[i]]);
	for(m=2;m<=lim;m<<=1) {
		k=m>>1;
		gn=qpow(3,(mod-1)/m);
		for(i=0;i<lim;i+=m) {
			g=1;
			for(j=0;j<k;++j,g=1LL*g*gn%mod) {
				tmp=1LL*x[i+j+k]*g%mod;
				x[i+j+k]=(x[i+j]-tmp+mod)%mod;
				x[i+j]=(x[i+j]+tmp)%mod;
			}
		}
	}
	if(opt==-1) {
		reverse(x+1,x+lim);
		int inv=qpow(lim,mod-2);
		for(i=0;i<lim;++i) x[i]=1LL*x[i]*inv%mod;
	}
}
int a[maxn],b[maxn];
bool vis[maxn];
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	int n,lim(1),m(0);
	cin>>n;
	for(int i=1,x;i<=n;++i) {
		cin>>x;
		a[x]=1,b[p-x]=1;
		if(x>m) m=x;
		if(p-x>m) m=p-x;
	}
	while(lim<(m<<1)) lim<<=1;
	for(int i=1;i<lim;++i) r[i]=(i&1)*(lim>>1)+(r[i>>1]>>1);
	ntt(a,lim,1);
	ntt(b,lim,1);
	for(int i=0;i<lim;++i) a[i]=1LL*a[i]*b[i]%mod;
	ntt(a,lim,-1);
	for(int i=p;i<lim;++i) if(a[i])
		vis[i-p]=1;
	for(int i=n;i<=p;++i) if(!vis[i]){
		int j=i+i;
		for(;j<=p;j+=i) if(vis[j]) break;
		if(j>p) return cout<<i<<'\n',0;
	}
    cout<<p+1<<'\n';
}

FFT代码

萌新代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=40007;
vector<int>prime;
bool vis[maxn];
inline void pre() {
	for(int i=2;i<maxn;++i) {
		if(!vis[i]) prime.emplace_back(i),vis[i]=1;
		for(int j:prime) {
			if(i*j>=maxn) break;
			vis[i*j]=1;
			if(i%j==0) break;
		}
	}
}
int work(int x) {
	for(int i:prime) if(x%i==0) return i;
	return x;
}
signed main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	pre();
	int T;
	cin>>T;
	while(T--) {
		int a,b,c;
		cin>>a>>b;
		if(a==b) {
			if(a==1) cout<<"-1 -1\n";
			else cout<<2<<' '<<a<<'\n';
			continue;
		}
		c=abs(a-b);
		if(c<2) {
			cout<<"-1 -1\n";
			continue;
		}
		cout<<work(c)<<' '<<c<<'\n';
	}
}