LCM Sum (hard version)（树状数组，筛因子）

目录

思路：

代码：

---

 

LCM Sum (hard version)

This version of the problem differs from the previous one only in the constraint on tt. You can make hacks only if both versions of the problem are solved.

You are given two positive integers ll and rr.

Count the number of distinct triplets of integers (i,j,k)(i,j,k) such that l≤irl≤i

Here lcm(i,j,k)lcm⁡(i,j,k) denotes the least common multiple (LCM) of integers ii, jj, and kk.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1051≤t≤105). Description of the test cases follows.

The only line for each test case contains two integers ll and rr (1≤l≤r≤2⋅1051≤l≤r≤2⋅105, l+2≤rl+2≤r).

Output

For each test case print one integer — the number of suitable triplets.

Example

input

Copy

5

1 4

3 5

8 86

68 86

6 86868

output

Copy

3
1
78975
969
109229059713337

Note

In the first test case, there are 33 suitable triplets:

• (1,2,3)(1,2,3),
• (1,3,4)(1,3,4),
• (2,3,4)(2,3,4).

In the second test case, there is 11 suitable triplet:

• (3,4,5)(3,4,5).

思路：

正难则反

1，讨论总的情况：（r-l+1）*(r-l-1)/6

2,讨论lcm的情况：lcm（i，j，k）lcm<3*k，=>lcm为k或者2*k

3，讨论i，j的情况：

当lcm为2*k时：

1)k/22t=3=>j=2/3*k

2)2*kkk/32i=k/2||k*2/5

当lcm为k时：

i

4,树状数组记载每个数作为i的可行情况数

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector<int>
#define pii pair<int,int>
#define pi 3.1415926
#define rep(i,l,r) for(int i=l;i<=r;++i)
#pragma GCC optimize(2)//
#pragma GCC optimize(3,"Ofast","inline")//
const int maxj=2e5+10,mod=1e9+7,inf=0x3f3f3f3f;
struct bit{
    int sum[maxj];
    int lowbit(int x){return x&-x;}
    void add(int x,int c){while(x<=maxj)sum[x]+=c,x+=lowbit(x);}
    int getsum(int x){int res=0;while(x)res+=sum[x],x-=lowbit(x);return res;}
 
}tree;
vector<pii>a[maxj];
int ans[maxj];
vec fac[maxj];//存因子
void solve(){
    int n;cin>>n;
    for(int i=1;i<maxj;++i){//存因子
        for(int j=i*2;j<maxj;j+=i){
            fac[j].emplace_back(i);
        }
    }
 
    for(int i=1;i<=n;++i){//
        int l,r;cin>>l>>r;
        a[r].push_back({l,i});//存数组，l，r
        int x=r-l+1;
        ans[i]=x*(x-1)*(x-2)/6;//正难则反
    }
 
    for(int r=1;r<maxj;++r){//既是k，又是r，暴力得出答案
        //公因子2*k，找r以内的因子
        for(int j=0;j<fac[r].size();++j){
            int x=fac[r][j];
            int cnt=0;//计数器
            for(int k=j+1;k<fac[r].size();++k){
                int y=fac[r][k];
                if(r%x==0&&r%y==0){
                    cnt+=1;
                }
            }
            tree.add(x,cnt);
        }
        //j为2/3*k
        //i是k/2
        if(r%6==0){
            tree.add(r/2,1);
        }
        //i是2/5*k
        if(r%15==0){
            tree.add(r*2/5,1);
        }
        for(auto i:a[r]){//计算（l，r-2），
            ans[i.second]-=(tree.getsum(r-2)-tree.getsum(i.first-1));
        }
    }
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);//与快读冲突
    int t;
    t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}