[数据结构与算法]Codeforces 1548B Integers Have Friends 尺取法 & Hdu 7073 Integers Have Friends 2.0 力能扛鼎随机算法

题意

定义数的好友组为一个集合$S$,取正整数$m>1,?x\in s,xmodm$为同一个数.
其中CF1548B的好友组必须是连续区间,而HDU7073没有这样的要求.
给定互不相同的$n$个整数,求这些整数中最大的好友组.

题解 CF1548B

如果两个数在模$m$的好友组中,则这两个数差的绝对值一定能被$m$整除.
借助这个特性,计算相邻数差的绝对值$d$,则如果$d$中有一个长度$len$区间的$gcd>1$,则原数组中这个长度为$len+1$的区间显然可以成为模$gcd$的好友组.
区间$gcd$满足右端点右移不上升,左端点右移不下降的性质,所以本题可以使用尺取法.
用数据结构预处理区间$gcd$,通过尺取法求出最长$gcd>1$区间长度,$+1$即为答案.
代码使用了$st$表,用线段树也可以.

#include<bits/stdc++.h> //Ithea Myse Valgulious
using namespace std;
const int yuzu=2e5;
typedef ll fuko[yuzu|10];
fuko a,lg2={-1};
struct sp_table {
  fuko gcd[21];
  void init(int n) {
    for (int i=1;i<=n;++i) gcd[0][i]=a[i];
    for (int i=1;i<=19;++i) {
      for (int j=1;j+(1<<i)-1<=n;++j)
        gcd[i][j]=__gcd(gcd[i-1][j],gcd[i-1][j+(1<<i-1)]);
    }
  }
  ll query(int l,int r) {
    int k=lg2[r-l+1];
    return __gcd(gcd[k][l],gcd[k][r-(1<<k)+1]);
  } 
}zw;
int main() {
  for (int i=1;i<=yuzu;++i) lg2[i]=lg2[i>>1]+1;
  for (int t=read();t--;) {
    int n,i;
    read(n);
    for (i=1;i<=n;++i) read(a[i]);
    for (i=1;i<n;++i) a[i]=abs(a[i+1]-a[i]);
    zw.init(n-1);
    int ans=0;
    for (i=1;i<n;++i) {
      for (;i+ans<n&&zw.query(i,i+ans)>1;++ans);
    }
    printf("%d\n",ans+1);
  }
}

题解 Hdu 7073

本题$a_i\le 4\times 10^{12}$.
显然$m$肯定是取质数最优.
我们会发现当$m=2$的时候,这$n$个数会分成两部分,答案为较大的那一部分.
所以答案肯定大于$\frac{n}{2}$.
也就是说,如果随机取两个不同的位置,这两个位置都在答案里的概率至少是$\frac{1}{4}$.
则随机抽取两个位置,然后检查差绝对值的所有质因子.
则每一次不能检查到答案区域的概率小于$\frac{3}{4}$,如果随机$20$次,则仍然会失误的概率小于$0.3\%$,对于$30$组数据总体全过的概率至少是$90\%$.如果你觉得这个概率仍然不够大,那么也可以随机更多次,时间稳够.
对于小于$4\times 10^{12}$的数,质因子最多只有$11$种.故此总复杂度最大为$11Kn$,时间可过.
代码里我不愿意用$rand$也不想用$mt19937$,就自己随便写了个伪随机,甚至不用初始化.
随机次数我随便写了个$18$次就过了,出题人也卡不了我.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
// #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) pc('-'),x=-x;
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
namespace ran {
  const unsigned k1=53,k2=109,mak=4294967295;
  ll sa,sb;
  ll rndll() {
    sa=(sa*k1+k2)&mak;
    sb=(sb*k2+k1)&mak;
    return (sa<<31)|sb;
  }
  ll rnd(ll l,ll r) {
    return rndll()%(r-l+1)+l;
  }
}
const int yuzu=2e6;
typedef ll fuko[yuzu|10];
fuko a,p,pr;
int main(){
  int t,i,n,ti;
  auto doing_prime=[&](int n) {
    int i,j;
    for (i=2;i<=n;++i) {
      if (!p[i]) pr[++*pr]=i;
      for (j=1;j<=*pr&&pr[j]*i<=n;++j) {
        p[pr[j]*i]=1;
        if (i%pr[j]==0) break;
      } 
    }
  };
  doing_prime(yuzu);
  for (scanf("%d",&t);t--;) {
    int zw=1;
    auto cal=[&](ll x,ll y) {
      int cnt=0,i;
      for (i=1;i<=n;++i) cnt+=a[i]%x==y;
      return cnt;
    };
    scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%lld",a+i);
    for (ti=18;ti--;) {
      int l=0,r=0;
      for (;l==r;) {
        l=ran::rnd(1,n);
        r=ran::rnd(1,n);
      }
      ll g=abs(a[r]-a[l]);
      for (i=1;i<=*pr&&pr[i]*pr[i]<=g;++i) {
        if (g%pr[i]==0) {
          zw=max(zw,cal(pr[i],a[l]%pr[i]));
          for (;g%pr[i]==0;g/=pr[i]);
        }
      }
      if (g>1) zw=max(zw,cal(g,a[l]%g));
    }
    printf("%d\n",zw);
  }
}

谢谢大家.