2021牛客多校1 H hashfunction FTT/NTT，数论

本文主要是介绍2021牛客多校1 H hashfunction FTT/NTT，数论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

H 题意

n个数哈希，策略是直接模一个数。求最小的不冲突模数
范围0-50w

H 思路

冲突时当且仅当|ai-aj|%m=0
换句话说，m不能是任何一对aiaj的约数，数的范围不大，如果我们能知道所有|ai-aj|，那么我们枚举m，判断下他每一个倍数有没有出现过，就可以判断m是否可以做答案。这个复杂度是调和级数，nlogn级别的。
下面问题在于我们如何知道所有的ai-aj。这里需要一个前置知识。我们把ai看作多项式f1中x^ai
的系数，aj同样处理。那么所有ai+aj可以通过对两个多项式进行卷积得出。（显然，卷积后如果 x^k 的系数不为0，说明有两项相乘为k的情况，根据多项式的生成方式，也就是ai+aj=存在）。那么如果是ai-aj呢？不难发现可以把aj放在x^-aj的系数上。但fft不支持这种操作，那我们可以整体给他上一个偏移量d，似的所有d-aj>=0，我们卷积完之后次数全部减d就可以了。

H 代码

#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#include<bitset>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=2100505;const int inf=0x3f3f3f3f;const int mod=998244353;const int g=3;//原根int n,m,k;int a[maxn],b[maxn]; int rv[maxn];int len,cnt;int binpow(int a,int b=mod-2){a%=mod;int res = 1;while(b>0){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}void change(){for(int i=0;i<len;i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<(cnt-1));}void NTT(int *c,int type){for(int i=0;i<len;i++)if(i<rv[i])	swap(c[i],c[rv[i]]);for(int mid=1;mid<len;mid<<=1){int wn=binpow(g,(mod-1)/(mid*2));if(type==-1)	wn=binpow(wn);for(int R=mid<<1,j=0;j<len;j+=R){int w=1;for(int k=0;k<mid;k++,w=(w*wn)%mod){int x=c[j+k],y=w*c[j+mid+k]%mod;c[j+k]=(x+y)%mod;c[j+mid+k]=(x-y+mod)%mod;}}}if(type==-1){int re=binpow(len);for(int i=0;i<len;i++)c[i]=c[i]*re%mod;}}void solve(){cin>>n;while(n--){int t;cin>>t;a[t]++;b[500005-t]++;}len=1,cnt=0;while(len<=1000000)  len*=2,cnt++;change();NTT(a,1);NTT(b,1);for(int i=0;i<=len;i++){a[i]=1ll*a[i]*b[i]%mod;}NTT(a,-1);bool ok=1;for(int i=1;;i++){ok=1;for(int j=i;j<500005;j+=i){if(a[j+500005]){ok=0;break;}}if(ok){cout<<i<<endl;return ;}}}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;//cin>>tn;for(int __=1;__<=tn;__++){solve();}}