[SDOI2014]数表

题目链接：Click here

Solution:

题目里关于\(a\)的限制一看就很麻烦，我们先把\(a\)放到一边

\[\sum_{i=1}^N \sum_{j=1}^M \sigma(gcd(i,j))\\ \]

看到这个\(gcd\)，那么我们就立即想到枚举它

\[\sum_{d=1}^N \sigma(d) \sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} [gcd(i,j)=1] \]

式子变成了我们熟悉的形式

\[\sum_{d=1}^N \sigma(d) \sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} \sum_{t|i} \sum_{t|j} \mu(t)\\ \sum_{d=1}^N \sigma(d) \sum_{t=1} ^{\lfloor \frac{N}{d} \rfloor}\mu(t) \lfloor \frac{N}{dt}\rfloor \lfloor \frac{M}{dt} \rfloor\\ \]

令\(T=dt\)

\[\sum_{T=1} ^N \lfloor \frac{N}{T}\rfloor \lfloor \frac{M}{T}\rfloor \sum_{d|T} \sigma(d) \mu({T \over d}) \]

令\(f(T)=\sum_{d|T} \sigma(d) \mu({T \over d})\)，这个函数是可以预处理的，然后再数论分块即可

考虑关于\(a\)的限制，事实上，在有\(a\)的限制的情况下，会改变的只是\(f(T)\)的值

当\(\sigma(d)>a\)时，\(\sigma(d)\)不对\(f(T)\)造成贡献，那么我们用一个树状数组来维护\(f\)值

我们把询问按照\(a\)值排序，每次对新加进来的数，枚举它的倍数，把贡献加上即可，对于每个数是\(\log^2 n\)

然后数论分块的过程中，树状数组查询区间和即可，每次询问为\(\sqrt n \log n\)

Code:

#include
#define int long long
using namespace std;
const int N=1e5+11;
const int mod=2147483647;
struct Gval{int v,id;}g[N];
struct Ask{int qn,qm,qa,id;}a[N];
int n,m,cnt,vis[N],p[N],lst=1;
int num[N],u[N],tr[N],ans[N];
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void prepare(){
	u[1]=1;g[1].v=1;g[1].id=1;num[1]=1;
	for(int i=2;im) swap(n,m);
	while(g[lst].v<=a[uid].qa&&lst

[SDOI2014]数表