个数两个相减(相加)先序知识
Describe
给定
个数 :
求的集合
注意:
指的是
中的每一个元素与
中的每一个元素相加,即
相关题型:Hash Function B-小圆前辈的素数
Solve
朴素双重循环复杂度为
,对于数据量大于
的问题显然无法解决。
考虑
我们将上述集合换一种表达式:
则对于,转化为
因此,我们只要将一个多项式中的的系数赋值为
,其他赋值为
。进行一遍FFT后,检验
的系数,若
的系数大于等于
,则
。
提示:对于减法,实际上是加上一个负数,因为负下标的问题,可以先统一加上一个偏移量,最后减去即可得到原值。
具体问题讲解
题面描述 [Hash Function]
给定一个集合
考虑,求最小的整数
,使得
无冲突,即若
,则
。
Slove
我们需要考虑的是
,都存在
.
上述结论很容易证明:
考虑:
,则
显然
如果,则
。则
不合法。
也就是说
,
的因子全都不满足条件,同时对于其他数,一定都是满足条件的,证明如下:
因为
;且
;则
说明,同时对于每一对
都成立,故该
合法。
综上所述:我们需要快速求出所有的
,并求出
的所有因子。
即我们需要求出
上述做法即可在内完成,根据经验,
中元素不超过
个,同时元素不超过
,用正向筛选法可以在
内筛选出所有因子。
代码:
#include <cstdio> #include <complex> #include <cmath> using namespace std; int n,m; typedef complex<double> CP; const int lim = 1<<21; const double Pi = acos(-1); const int P = 500001; CP a[lim],b[lim]; bool vis[lim]; void FFT(CP *x,int lim,int inv) // 板子而已 { int bit = 1,m; CP stand,now,temp; while((1<<bit) < lim) ++bit; for (int i = 0; i < lim; ++i) { m = 0; for (int j = 0; j < bit; ++j) if(i & (1<<j)) m |= (1<<(bit-j-1)); if(i < m) swap(x[m],x[i]); } for (int len = 2; len <= lim; len <<= 1) { m = len >> 1; stand = CP(cos(2*Pi/len),inv*sin(2*Pi/len)); for (CP *p = x; p != x+lim; p += len) { now = CP(1,0); for (int i = 0; i < m; ++i,now*=stand) { temp = now * p[i+m]; p[i+m] = p[i] - temp; p[i] = p[i] + temp; } } } if(inv == -1) for (int i = 0; i < lim; ++i) x[i].real(x[i].real()/lim); } bool check(int x) { for (int i = x; i <= P; i += x) { if (vis[i] == 1) return 0; } return 1; } int main() { int x; scanf("%d",&n); for (int i = 0; i < n; ++i) { scanf("%d",&x); a[x].real(1); b[P - x].real(1); // 负数做偏移 } int num = 1 << 20; FFT(a,num,1); FFT(b,num,1); for (int i = 0; i < num; ++i) a[i] *= b[i]; FFT(a,num,-1); for (int i = 0; i <= num; ++i) { x = (int)floor(a[i].real()+0.5); if (x > 0) vis[abs(i - P)] = 1; } for (int i = n; i < P+1; ++i) if (check(i)) { printf ("%d\n",i); break; } return 0; }