传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3529
其中
预处理sigma,u,在a固定的情况下就可以预处理F计算答案
考虑离线,按a升序排列询问
那么从 a->a‘ 的时候,对于满足
的d
用树状数组更新F的前缀和
Code:
#include<cstdio> #include<iostream> #include<algorithm> #include<cctype> using namespace std; const int maxn=1e5+5; int mx; int d[maxn]; inline int lowbit(int x){return x&-x;} int get(int x){ int ans=0; while(x)ans+=d[x],x-=lowbit(x); return ans; } void updata(int x,int f){ while(x<=mx)d[x]+=f,x+=lowbit(x); } struct qes{int n,m,a,id;bool operator<(const qes oth)const{return a<oth.a;}}Q[maxn]; int anss[maxn]; int getint(){ int res=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))res=res*10+c-'0',c=getchar(); return res; } bool notp[maxn]; int p[maxn],u[maxn]; pair<int,int> sig[maxn]; void init(int maxn){ u[1]=1; for(int i=2;i<maxn;i++){ if(!notp[i]){ p[++p[0]]=i;u[i]=-1; }for(int j=1;i*p[j]<maxn&&j<=p[0];j++){ notp[i*p[j]]=1; if(i%p[j]==0){ u[i*p[j]]=0;break; }else u[i*p[j]]=-u[i]; } }for(int i=1;i<maxn;i++) for(int j=i;j<maxn;j+=i)sig[j].first+=i; for(int i=1;i<maxn;i++)sig[i].second=i; sort(sig+1,sig+maxn); } int main(){ int T=getint(); for(int i=1;i<=T;i++){ Q[i].n=getint();Q[i].m=getint(); if(Q[i].n>Q[i].m)swap(Q[i].n,Q[i].m); Q[i].a=getint();Q[i].id=i; mx=max(mx,Q[i].n); }init(mx+1); sort(Q+1,Q+1+T); int lasta=1; for(int i=1;i<=T;i++){ int newa=upper_bound(sig+1,sig+mx,make_pair(Q[i].a+1,-1))-sig-1; for(int j=lasta;j<=newa;j++) for(int k=sig[j].second;k<=mx;k+=sig[j].second) updata(k,sig[j].first*u[k/sig[j].second]); for(int j=1,k;j<=Q[i].n;j=k+1){ k=min(Q[i].n/(Q[i].n/j),Q[i].m/(Q[i].m/j)); anss[Q[i].id]+=(get(k)-get(j-1))*(Q[i].n/j)*(Q[i].m/j); }lasta=newa+1; }for(int i=1;i<=T;i++)printf("%d\n",anss[i]&0x7fffffff); return 0; }