根号分治

常见于含有两数相乘的题目中,或者数据范围在根号上下时可采用不同复杂度的算法平衡总复杂度

例题1:D. Another Problem about Beautiful Pairs

求i,j对,满足$a_ia_j==i-j(i>j)$,n最大是$210^5$
注意到,在$a_i$较大时,适合直接暴力枚举,因为没枚举几次就超过边界了,在$a_i$较小时,不适枚举,

所以划分一个界限,大于$\sqrt{n}$的枚举,小于$\sqrt{n}$的只计算$\sqrt{n}$次,
这么划分的作用是两边刚好全部包括在内
如果$a_i$小的话$a_j$可能大,但是这部分被大于$\sqrt{n}$的部分枚举到了,减少了无效枚举
所以代码:

void solve(){
  ll n,ans=0; cin>>n;
  vector<ll> a(n+1);
  for(int i=1;i<=n;i++) cin>>a[i];
  ll fj=sqrt(n);
  for(int i=1;i<=n;i++){
    if(a[i]>n) continue;
    if(a[i]<=fj) 
	    for(int x=1,j=i+a[i];x<=fj&&j<=n;x++,j+=a[i]) if(j-i==a[i]*a[j]) ans++;
    else{
      for(int j=i-a[i];j>=1;j-=a[i]) if(i-j==a[i]*a[j]) ans++;
      for(int j=i+a[i];j<=n;j+=a[i]) if(j-i==a[i]*a[j]) ans++;
    }
  }
  cout<<ans<<endl;
}

例题2:F. Remainder Problem

操作: 给x位置加上y
查询: 求$\sum_{i=1}^n a_i(i \mod x==y)$
n为$5*10^5$

查询时,如果是x较大,查询时暴力也能计算,但是x较小时,查询起来会很麻烦,但是可以预处理一下,开一个数组,sum[x][y]表示i mod x == y的所有数字之和
所以依旧分开计算,当x小于$\sqrt{n}$时,采用方法2预处理,x大于$\sqrt{n}$时采用方法1,暴力计算
对于每个输入的x,在数组中计算一次,再去预处理数组中加一下,两者合起来都只需要700左右的循环次数,执行比较快,注意别被卡常即可,用C的输入输出方法

代码:

#include<bits/stdc++.h>
using namespace std;
int sum[710][710],a[500010];
int main(){
  int q; scanf("%d",&q);
  for(int j=1;j<=q;j++){
    int op,x,y; scanf("%d%d%d",&op,&x,&y);
    if(op==1){
      for(int i=1;i<700;++i) sum[i][x%i]+=y;
      a[x]+=y;
    }
    else{
      if(x<700) cout<<sum[x][y]<<endl;
      else{
        int ans=0;
        for(int i=y;i<=500000;i+=x) ans+=a[i];
        printf("%d\n",ans);
      }
    }
  }
}