题解：CF2094H La Vaca Saturno Saturnita
ctzm
·
·
题解
VP 时想到的诡异非根号分治但通过做法。其实已经想了一个根号分治了，但感觉 Div.4 放根号分治有点遥遥领先了，所以没敢写。
题意简述：给定长度为 n 的正整数数列 a，模拟以下伪代码函数：
function f(k, a, l, r):
ans := 0
for i from l to r (inclusive):
while k is divisible by a[i]:
k := k/a[i]
ans := ans + k
return ans
函数调用 q 次，每次给出参数 k,l,r，回答结果。
---
本题考查敢写。VP 时感觉此做法过于诡异，不敢写，费劲优化才逐渐信任此做法。
注意到 $k$ 一旦除以其他数，至少减半，所以实际次数为 $\log$ 量级。并且除以某个数后会直接把 $k$ 潜在的因子全部榨干（以后再遇到这个数就不会触发除了），实际上是不重复的，最坏是 $8! = 40320$，共 $7$ 次（$1$ 不算在内）。
这意味着实际上很多的遍历到的 $a_i$ 并不对 $k$ 产生影响，考虑如何快速找到使得一个 $k$ 降低的位置，就可以计算一段区间的贡献（$k$ 不变的一段），这个位置就是在 $l$ 后面最近的 $i$ 使得 $a_i | k$。这样子 $f(k,a,l,r)$ 就变成了 $k \times (i-l) + k_{new} + f(k_{new},a,i+1,r)$。
显然你不能开 $10^{10}$ 的空间，注意到 $10^5$ 以内的数因数个数肯定不会很多（实际最多为 $128$ 个），我们直接枚举其因数，然后用二分求最近的 $i$ 即可。
笔者 VP 时怕 TLE，改写成了一个奇奇怪怪的离线 + 队列，就没有二分的 $\log$ 了，交上去还不到时限的十分之一。
尽可能添加了自认为较为详细的注释，辅助代码理解可能会更好一些。~~（当然也可能需要更多的精力来理解我的丑陋代码）~~
运算量为 $50000 \times 128 \times 7 = 44800000$，足以通过本题（[389 ms 144900 KB](https://codeforces.com/contest/2094/submission/323763339)）。本题甚至开了 4s 时限。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int t,n,q,a[100010];
long long ans[50050];
vector<int> f[100010];//f[i] i的因子 不包括 1
struct qu{
int id,k,r;
};
queue<qu> b[100010];//离线查询 下标就是l
queue<int> c[100010];//O(1)求最近i的队列
void init(){//预处理因子
for(int i=2;i<=N;i++){
for(int j=i;j<=N;j+=i)f[j].push_back(i);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cout.tie(0);
cin>>t;
init();
while(t--){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
c[a[i]].push(i);
}
for(int i=1;i<=q;i++){
int k,l,r;
cin>>k>>l>>r;
b[l].push({i,k,r});
}
for(int i=1;i<=n;i++){
while(!b[i].empty()){
qu _=b[i].front();
b[i].pop();
int new_l=_.r+1;//找最近的i，添加完贡献后就变成了另一个函数
//由于函数的l转化后单调递增 所以队列就以l为下标 循环里也是i从小到大
for(int j:f[_.k]){
while(!c[j].empty()&&c[j].front()<i)c[j].pop();
if(!c[j].empty())new_l=min(new_l,c[j].front());
}
if(new_l>_.r)ans[_.id]+=1ll*(_.r-i+1)*_.k;//找不到的话就结束
else{
ans[_.id]+=1ll*(new_l-i)*_.k;//添加贡献
while(_.k%a[new_l]==0)_.k/=a[new_l];
ans[_.id]+=_.k; //添加贡献
if(new_l+1<=n)b[new_l+1].push(_);
}
}
}
for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
//下面都是多测清空 保险全清了
for(int i=1;i<=q;i++)ans[i]=0;
for(int i=1;i<=n;i++){
while(!c[a[i]].empty())c[a[i]].pop();
while(!b[i].empty())b[i].pop();
a[i]=0;
}
}
return 0;
}
// 50000 * 128 * 7 = 44800000
// https://codeforces.com/contest/2094/submission/323763339
```