E. Josuke and Complete Graph 数论分块

shi5 / 2023-09-01 / 原文

题意：很简单，给你l，r，让你输出对于这个区间中任意两个不同的数字的gcd组成的set的大小是多大。至于题面，我只能说，聪明人早就看出来那些图啊边啊啥的都是唬人的。

做法：显然我们是要去枚举的，但是我们不能去枚举选的那两个数字。所以我们选择枚举gcd有哪些。这些gcd又分两种：

第一种，假如一个数字在lr区间上，而且两倍的它依旧在区间上。符合这个条件的所有数为我们要统计的。这一步我们o1计算即可。

第二种，假如区间左端点除以一个数向上取整得到的数与区间右端点除以一个数向下取整得到的数不同，那么这个数就合法了。

现在我们该如何加速上述的过程呢？考虑数论分块。用数论分块求出右端点，然后减去当前的左端点加1就是符合的了，不过要注意边界。

#include<bits/stdc++.h>
#define de cout<<111<<"\n";
#define fi first
#define se second
#define ll long long
#define kx(a,b) ((a*b)%mod)
#define kplus(a,b) ((a+b)%mod)
#define lowbit(x) x&(-x);
#define up(a,b) ((a-1ll)/b+1ll)
typedef __int128 Int;
using namespace std;
const int N=1000010;
const ll mod=998244353;
void solve(){
    ll L,R;
    cin>>L>>R;
    ll ans=max(R/2+1,L)-L;
    L--;
    for(ll l=1,r;l<=L;l=r+1){
        r=min(L,L/(L/l));
        ll a=L/l+1ll;
        ans+=max(0ll,min(R/(a+1),r)-l+1ll);
    }
    cout<<ans<<"\n";
}
signed main(){
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin>>t;
  while(t--)
    solve();
}