[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} floor} sum_{j=1}^{lfloor frac{M}{d} floor} [gcd(i,j)=1] ]

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

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

令(T=dt)

[sum_{T=1} ^N lfloor frac{N}{T} floor lfloor frac{M}{T} floor 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<bits/stdc++.h>
#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;i<N;i++){
		g[i].id=i;
		if(!vis[i]) p[++cnt]=i,u[i]=-1,g[i].v=i+1,num[i]=i;
		for(int j=1;j<=cnt&&i*p[j]<N;j++){
			vis[i*p[j]]=1;
			if(i%p[j]==0){
				num[i*p[j]]=num[i]*p[j];
				if(i*p[j]==num[i*p[j]]) g[i*p[j]].v=g[i].v+i*p[j];
				else g[i*p[j]].v=g[i/num[i]].v*g[num[i*p[j]]].v;
				break;
			}
			g[i*p[j]].v=(g[i].v*g[p[j]].v);
			num[i*p[j]]=p[j];u[i*p[j]]=-u[i];
		}
	}
}
int lowbit(int x){return x&(-x);}
void add(int x,int v){
	for(;x<N;x+=lowbit(x)) tr[x]=(tr[x]+v)&mod;
}
int query(int x){
	int re=0;
	for(;x;x-=lowbit(x)) re=(re+tr[x])&mod;
	return re;
}
inline bool cmp(Ask x,Ask y){
	return x.qa<y.qa;
}
inline bool ucmp(Gval x,Gval y){
	return x.v<y.v;
}
void solve(int uid){
	n=a[uid].qn,m=a[uid].qm;
	int Id=a[uid].id;
	if(n>m) swap(n,m);
	while(g[lst].v<=a[uid].qa&&lst<N){
		int i=g[lst].id;
		for(int j=i;j<N;j+=i)
			add(j,(g[lst].v*u[j/i]));
		++lst;
	}
	for(int i=1,j;i<=n;i=j+1){
		j=min(n/(n/i),m/(m/i));
		int tmp=(n/i)*(m/i)&mod;
		ans[Id]+=tmp*(query(j)-query(i-1))&mod;
		ans[Id]=ans[Id]&mod;
	}
}
signed main(){
	prepare();
	int t=read();
	for(int i=1;i<=t;i++){
		a[i].qn=read(),a[i].qm=read();
		a[i].qa=read();a[i].id=i;
	}
	sort(a+1,a+t+1,cmp);
	sort(g+1,g+N,ucmp);
	for(int i=1;i<=t;i++) solve(i);
	for(int i=1;i<=t;i++) printf("%lld
",ans[i]&mod);
    return 0;
}

[SDOI2014]数表