宁夏建设网站的公司,滨海做网站公司,桥头镇网站建设公司,图片下载网站哪个好Hash Function 文章目录题意#xff1a;题解#xff1a;代码NTT代码FFT代码题意#xff1a;
给定n个互不相同的数#xff0c;找一个最小的模域#xff0c;使得它们在这个模域下互不相同。n5e5
题解#xff1a;
考虑两个数a和b#xff0c;a与b模m余数相同#xf…Hash Function
文章目录题意题解代码NTT代码FFT代码题意
给定n个互不相同的数找一个最小的模域使得它们在这个模域下互不相同。n5e5
题解
考虑两个数a和ba与b模m余数相同当且仅当|a-b|能被m整除。 这样问题就转化成找到一个最下的m使得m不是任意一个|ai-aj|约数(不会被m整除) n5e5,所以直接暴力n2肯定不行 这时就要用到FFT/NTT加速 算N个数两两之差当然用FFT利用多项式相乘即指数相加来做(加减用指数相乘用系数) 刚接触FFT的同学可能不明白减法怎么用FFT的模板不是乘法吗 我们这样想FFT可以快速求两个多项式的乘积并求出每个指数所对应的系数两个数相乘指数相加也就是如果我有一个多项式的指数为xy对应的系数都为1另一个多项式的指数为zw对应的系数都为1相乘后会得到指数为xz,xw,zy,yw,那如果我们将z和w分别为-x-y那就会得到x-xx-yy-xy-y这不正是x和y任意两数的差该差是否存在就看他们的系数是否为1 这样就在N*logN求出所有差注意FFT中是没有指数为负的所有我们加入一个偏移量MAX让MAX-x最后得到结果再加回去就行 回到本题要求是求最小的m不是任意两数差的约数。现在我们求出所有的差并标记然后枚举这个m如果这个m的倍数均没有被标记输出m 所以这算是个模板题了会使用FFT/NTT板子
代码
NTT代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int maxn5e5100;
const int mx5e5;
const int mod998244353;
namespace IO{templatetypename Tvoid write(T x){if(x0){putchar(-);x-x;}if(x9){write(x/10);}putchar(x%100);}templatetypename T void read(T x){x 0;char ch getchar();int f 1;while(!isdigit(ch)){if(ch -)f*-1;chgetchar();}while(isdigit(ch)){x x*10(ch-0);chgetchar();}x*f;}
};
namespace Math{ll w;const int p::mod;struct complex{ll real,imag;complex(ll a0,ll b0){reala;imagb;}friend complex operator*(const complexa,const complexb){complex ans;ans.real((a.real*b.real%pa.imag*b.imag%p*w%p)%pp)%p;ans.imag((a.real*b.imag%pa.imag*b.real%p)%pp)%p;return ans;}};ll x1,x2;ll ksm(ll a,ll b,ll p){ll ans1;while(b){if(b1) ans(ans*a)%p;a(a*a)%p;b1;}return ans;}ll ksm(complex a,ll b,ll p){complex ans(1,0);while(b){if(b1) ansans*a;aa*a;b1;}return ans.real%p;}bool Cipolla(ll n,llx0,llx1){n%p;if(ksm(n,(p-1)1,p)p-1) return false;ll a;while(true){arand()%p;w((a*a%p-n)%pp)%p;if(ksm(w,(p-1)1,p)p-1) break;}complex x(a,1);x0(ksm(x,(p1)1,p)p)%p;x1(p-x0p)%p;return true;}
};namespace NTT{#define mul(x,y) ((1ll*x*ymod?x*y%mod:1ll*x*y))#define dec(x,y) (1ll*x-y0?1ll*x-ymod:1ll*x-y)#define add(x,y) (1ll*xymod?1ll*xy-mod:1ll*xy)#define ck(x) (xmod?x-mod:x)typedef vectorint Poly;int ksm(int a,int n,int mod::mod){int res1;while(n){if(n1)res1ll*res*a%mod;a1ll*a*a%mod;n1;}return res;}const int img86583718;const int g3,INVksm(g,mod-2);const int mx21;int R[maxn2],deer[2][mx][maxn2],inv[maxn2];void init(const int t) {for(int p 1; p t; p) {int buf1 ksm(g, (mod - 1) / (1 p));int buf0 ksm(INV, (mod - 1) / (1 p));deer[0][p][0] deer[1][p][0] 1;for(int i 1; i (1 p); i) {deer[0][p][i] 1ll * deer[0][p][i - 1] * buf0 % mod;deer[1][p][i] 1ll * deer[1][p][i - 1] * buf1 % mod;}}inv[1] 1;for(int i 2; i (1 t); i)inv[i] 1ll * inv[mod % i] * (mod - mod / i) % mod;}int NTT_init(int n) {int lim 1, l 0;while(lim n) lim 1, l ;for(int i 0; i lim; i)R[i] (R[i 1] 1) | ((i 1) (l - 1));return lim;}void ntt(Poly A, int type, int lim) {A.resize(lim);for(int i 0; i lim; i)if(i R[i])swap(A[i], A[R[i]]);for(int mid 2, j 1; mid lim; mid 1, j) {int len mid 1;for(int pos 0; pos lim; pos mid) {int *wn deer[type][j];for(int i pos; i pos len; i, wn) {int tmp 1ll * (*wn) * A[i len] % mod;A[i len] ck(A[i] - tmp mod);A[i] ck(A[i] tmp);}}}if(type 0) {for(int i 0; i lim; i)A[i] 1ll * A[i] * inv[lim] % mod;}}Poly poly_mul(Poly A, Poly B) {int deg A.size() B.size() - 1;int limit NTT_init(deg);Poly C(limit);ntt(A, 1, limit);ntt(B, 1, limit);for(int i 0; i limit; i)C[i] 1ll * A[i] * B[i] % mod;ntt(C, 0, limit);C.resize(deg);return C;}Poly poly_inv(Poly f, int deg) {if(deg 1)return Poly(1, ksm(f[0], mod - 2));Poly A(f.begin(), f.begin() deg);Poly B poly_inv(f, (deg 1) 1);int limit NTT_init(deg 1);ntt(A, 1, limit), ntt(B, 1, limit);for(int i 0; i limit; i)A[i] B[i] * (2 - 1ll * A[i] * B[i] % mod mod) % mod;ntt(A, 0, limit);A.resize(deg);return A;}Poly poly_idev(Poly f) {int n f.size();for(int i n - 1; i-10 ; -- i) f[i] 1ll * f[i - 1] * inv[i] % mod;f[0] 0;return f;}Poly poly_dev(Poly f) {int n f.size();for(int i 1; i n; i) f[i - 1] 1ll * f[i] * i % mod;f.resize(n - 1);return f;}Poly poly_ln(Poly f, int deg) {Poly A poly_idev(poly_mul(poly_dev(f), poly_inv(f, deg)));return A.resize(deg), A;}Poly poly_exp(Poly f, int deg) {//cerrdegendl;if(deg 1)return Poly(1, 1);Poly B poly_exp(f, (deg 1) 1);B.resize(deg);Poly lnB poly_ln(B, deg);for(int i 0; i deg; i)lnB[i] ck(f[i] - lnB[i] mod);int limit NTT_init(deg 1);ntt(B, 1, limit), ntt(lnB, 1, limit);for(int i 0; i limit; i)B[i] 1ll * B[i] * (1 lnB[i]) % mod;ntt(B, 0, limit);B.resize(deg);return B;}Poly poly_pow(Polyf,int k){fpoly_ln(f,f.size());for(autox:f)x1ll*x*k%mod;return poly_exp(f,f.size());}Poly power(Poly f,int k1,int k2,int deg){int s0;while(f[s]0sf.size())s;if(1ll*s*k1deg){return vectorint(deg);}int Invksm(f[s],mod-2,mod);int Mulksm(f[s],k2);deg-s;for(int i0;ideg;i)f[i]f[is];f.resize(deg);for(int i0;ideg;i)f[i]1ll*f[i]*Inv%mod;auto res1poly_ln(f,deg);for(int i0;ires1.size();i)res1[i]1ll*res1[i]*k1%mod;auto res2poly_exp(res1,deg);for(int i0;ideg;i)res2[i]1ll*res2[i]*Mul%mod;degs;int nows*k1;Poly res;res.resize(deg);for(int ideg-1;inow;--i)res[i]res2[i-now];for(int inow-1;i0;--i)res[i]0;return res;}Poly Poly_Sqrt(Polyf,int deg){if(deg1)return Poly(1,1);Poly A(f.begin(),f.begin()deg);Poly BPoly_Sqrt(f,(deg1)1);Poly IBpoly_inv(B,deg);int limNTT_init(deg1);ntt(A,1,lim),ntt(IB,1,lim);for(int i0;ilim;i){A[i]1ll*A[i]*IB[i]%mod;}ntt(A,0,lim);for(int i0;ideg;i){A[i](1ll*A[i]B[i])%mod*inv[2]%mod;}A.resize(deg);return A;}Poly Sqrt(Polyf,int deg){const int Powksm(2,mod-2);int k11;if(f[0]!1){k1ksm(f[0],mod-2);for(int i1;if.size();i){f[i]1ll*k1*f[i]%mod;}ll x0,x1;assert(Math::Cipolla(f[0],x0,x1));k1min(x1,x0);f[0]1;}auto Lnpoly_ln(f,deg);for(int i0;if.size();i){Ln[i]1ll*Ln[i]*Pow%mod;}auto Exppoly_exp(Ln,deg);for(int i0;iExp.size();i)Exp[i]1ll*Exp[i]*k1%mod;return Exp;}Poly poly_sin(Polyf,int deg){Poly A(f.begin(),f.begin()deg);Poly B(deg),C(deg);for(int i0;ideg;i){A[i]1ll*A[i]*img%mod;}Bpoly_exp(A,deg);Cpoly_inv(B,deg);const int inv2iksm(img1,mod-2);for(int i0;ideg;i){A[i]1ll*(1ll*B[i]-C[i]mod)%mod*inv2i%mod;}return A;}Poly poly_cos(Polyf,int deg){Poly A(f.begin(),f.begin()deg);Poly B(deg),C(deg);for(int i0;ideg;i){A[i]1ll*A[i]*img%mod;}Bpoly_exp(A,deg);Cpoly_inv(B,deg);const int inv2ksm(2,mod-2);for(int i0;ideg;i){A[i](1ll*B[i]C[i])%mod*inv2%mod;}return A;}Poly poly_arcsin(Poly f,int deg){Poly A(f.size()),B(f.size()),C(f.size());Apoly_dev(f);Bpoly_mul(f,f);for(int i0;ideg;i){B[i]dec(mod,B[i]);}B[0]add(B[0],1);CPoly_Sqrt(B,deg);Cpoly_inv(C,deg);Cpoly_mul(A,C);Cpoly_idev(C);return C;}Poly poly_arctan(Poly f, int deg) {Poly A(f.size()), B(f.size()), C(f.size());A poly_dev(f);B poly_mul(f, f);B[0] add(B[0], 1);C poly_inv(B, deg);C poly_mul(A, C);C poly_idev(C);C.resize(deg);return C;}
};
using NTT::Poly;
using namespace IO;
int n,t;
Poly a,b;
bool vis[maxn];signed main(){//freopen(in.txt,r,stdin);//clock_t c1 clock();NTT::init(NTT::mx-1);//for(auto x:tmp)cerrx ;cerrendl;a.resize(maxn),b.resize(maxn);int n;read(n);if(n1){cout1endl;return 0;}for(int i0;in;i){int x;read(x);a[x]1;b[mx-x]1;}auto resNTT::poly_mul(a,b);for(int imx;i2*mx;i){if(res[i]){vis[i-mx]1;}}bool flag0;for(int i1;imx1;i){int now0;for(int ji;jmx;ji){now|(vis[j]!0);if(now)break;}if(!now){coutiendl;flag1;break;}}return 0;
}FFT代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N2e650;
const double piacos(-1);
ll r[N],bits;
complexdoubleA[N],B[N],w[N];
int dp[500005], vis[500005];
void FFT(complexdouble *P,ll op,ll N)
{for(ll i1;iN;i){if(ir[i])swap(P[i],P[r[i]]);}for(ll i1;iN;i1){for(ll pi1,j0;jN;jp){for(ll k0;ki;k){complexdoubleWw[N/i*k];W.imag(W.imag()*op);complexdouble XP[jk],YW*P[jki];P[jk]XY;P[jki]X-Y;}}}
}ll a[N],b[N],cnt[N];void solve(ll *a,ll *b,ll n,ll m)
{ll len;for(len1,bits0;lennm;len1)bits;bits--;for(ll i0;ilen;i)A[i].real(0),A[i].imag(0),B[i].real(0),B[i].imag(0);for(ll i0;in;i)A[i].real(a[i]);for(ll i0;im;i)B[i].real(b[i]);for(ll i0;ilen;i)r[i](r[i1]1)|((i1)bits);for(ll i0;ilen;i)w[i].real(cos(pi/len*i)),w[i].imag(sin(pi/len*i));FFT(A,1,len);FFT(B,1,len);for(ll i0;ilen;i)A[i]A[i]*B[i];FFT(A,-1,len);for(ll i0;inm;i)a[i](ll)(A[i].real()/len0.5);
}ll hh[1500150];
ll cii0;int main()
{ll n,m,k,x;scanf(%lld,n);for(ll i0;in;i){scanf(%lld,x);a[x]1;b[500050-x]1;}solve(a,b,500050,500050);//printf(a%lld \n,a[1000]);for(ll i0;i1000100;i){if(a[i]!0)hh[cii]abs(i-500050);}int Max0;for(ll i0;icii;i){if(hh[i]Max){Maxhh[i];}dp[hh[i]]1;}int ansMax1;for(int iMax;in;i--){if(dp[i]0){ansi;continue;}if(vis[i]1){continue;}for(int j2;j*ji;j){if(i%j0){vis[j]1;vis[i/j]1;dp[j]1;dp[i/j]1;}}}printf(%d\n,ans);return 0;
}
