个数两个相减(相加)先序知识

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;
}