提高培优班 D14T4 简单三元组计数题解
题意简述
已知 l,r , 求 \underset {l\le i<j<k\le r}\Sigma lcm(i,j,k)\ge i+j+k
思路
正难则反
\underset {l\le i<j<k\le r}\Sigma lcm(i,j,k)\ge i+j+k\to tot-\underset {l\le i<j<k\le r}\Sigma lcm(i,j,k)< i+j+k
\because i+j+k<3k\ and\ k\mid lcm(i,j,,k)
\therefore lcm(i,j,k)=k\ or\ lcm(i,j,k)=2k \ \ \ \ \alpha
显然，枚举 k 复杂度错误。
令 lcm(i,j,k)=x,i=\frac{x}{a},j=\frac{x}{b},k=\frac{x}{c}
则 \frac{1}{a}+\frac{1}{b}+\frac{1}{c}>1,a>b>c
由 \alpha 得， c=1/2
考虑 c=2 的情况，
易得出，只有 \begin{cases}a=4\\b=3\\c=2\end{cases} \begin{cases}a=5\\b=3\\c=2\end{cases} 满足情况。
那么可以得出，$i:j:k=3:4:6/6:10:15$
这样数数就很简单了
再考虑 c=1 的情况，
显然，此时 i,j\mid k
令 cnt_i 表示 i 在 [l,r] 中，约数个数（不含 i )
则答案为 \Sigma C_{cnt_i}^2
这里我们可以直接考虑离线，从 max\_r 开始倒取，给 i 的倍数 +1 即可
单点修改，区间查值，就是树状数组板子。
code
#define int long long
const int N=2e5+5000;
int cnt[N],t[N],ans[N],maxr;
vector<pair<int,int> >e[N];
inline int calc(int a){return a*(a-1)/2*(a-2)/3;}
inline void add(int x,int d){for(;x<=maxr;x+=x&-x)t[x]+=d;}
inline int ask(int x){int ret=0;for(;x;x^=x&-x)ret+=t[x];return ret;}
signed main(){
int T;read(T);
for(int i=1,l,r;i<=T;i++){
read(l,r);
ans[i]=calc(r-l+1)-max(0ll,r/6-(l+2)/3+1)-max(0ll,r/15-(l+5)/6+1);
e[l].emplace_back(make_pair(i,r));maxr=max(maxr,r);
}for(int i=maxr;i;i--){
for(int j=i<<1;j<=maxr;j+=i) add(j,cnt[j]++);//log^2 n
for(pair<int,int> v:e[i]) ans[v.first]-=ask(v.second)-ask(i-1);
}
for(int i=1,l,r;i<=T;i++) printf("%lld\n",ans[i]);
return 0;
}
