洛谷P3312 [SDOI2014]数表（莫比乌斯反演+树状数组）
不考虑$a$的影响
设$f(i)$为$i$的约数和
$$ans=sumlimits_{i=1}^nsumlimits_{j=1}^nf(gcd(i,j))$$
$$=sumlimits_{d=1}^nf(d)sumlimits_{i=1}^{lfloor frac n d floor}sumlimits_{j=1}^{lfloor frac m d floor } [gcd(i,j)==1]$$
这个东西直接反演一下
$$=sumlimits_{d=1}^nf(d)sumlimits_{i=1}^{lfloor frac n d floor}mu(i) lfloor frac n {di} floor lfloor frac m {di} floor$$
然后转为枚举$di$
$$=sumlimits_{D=1}^{n}sumlimits_{d|D}f(d)mu(frac D d) lfloor frac n {D} floor lfloor frac m {D} floor$$
对于每一个$i$可以用整除分块把它前缀和的贡献算出来，然后用树状数组动态维护前缀和
然后我们考虑$a$的限制。把所有询问离线按$a$排序，从小到大处理处理询问，每处理到一个询问就把所有的$f(d)<=a$的$d$的贡献都累加起来，直接树状数组查询一下就可以了
然后听大佬们说这题取模直接自然溢出就可以了，然后不知道为啥最后还要$&$一个$0x7fffffff$
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #define ui unsigned int 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 char sr[1<<21],z[20];int C=-1,Z; 21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 22 inline void print(int x){ 23 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 24 while(z[++Z]=x%10+48,x/=10); 25 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 26 } 27 const int N=1e5; 28 int p[N];ui mu[N+5],f[N+5],c[N+5],ans[N+5]; 29 int a[N+5],m,q,n,vis[N+5]; 30 struct node{ 31 int n,m,val,id; 32 node(){} 33 node(int n,int m,int val,int id):n(n),m(m),val(val),id(id){} 34 inline bool operator <(const node &b)const 35 {return val<b.val;} 36 }t[N]; 37 inline bool cmp(const int &a,const int &b){return f[a]<f[b];} 38 inline void add(int x,ui y){ 39 for(;x<=N;x+=x&-x) c[x]+=y; 40 } 41 inline ui query(int x){ 42 ui res=0; 43 for(;x;x-=x&-x) res+=c[x]; 44 return res; 45 } 46 void init(){ 47 mu[1]=1; 48 for(int i=2;i<=N;++i){ 49 if(!vis[i]) p[++m]=i,mu[i]=-1; 50 for(int j=1;j<=m&&p[j]*i<=N;++j){ 51 vis[i*p[j]]=1; 52 if(i%p[j]==0) break; 53 mu[i*p[j]]=-mu[i]; 54 } 55 } 56 for(int i=1;i<=N;++i) 57 for(int j=i;j<=N;j+=i) 58 f[j]+=i; 59 for(int i=1;i<=N;++i) a[i]=i; 60 sort(a+1,a+1+N,cmp); 61 } 62 int main(){ 63 // freopen("testdata.in","r",stdin); 64 init(); 65 q=read(); 66 for(int i=1,x,y,z;i<=q;++i){ 67 x=read(),y=read(),z=read(); 68 if(x>y) swap(x,y);cmax(z,0); 69 t[i]=node(x,y,z,i); 70 } 71 sort(t+1,t+q+1); 72 for(int i=1,j=1,k;i<=q;++i){ 73 for(;f[a[j]]<=t[i].val;++j) 74 for(k=a[j];k<=N;k+=a[j]) 75 add(k,f[a[j]]*mu[k/a[j]]); 76 for(int l=1,r;l<=t[i].n;l=r+1){ 77 r=min(t[i].n/(t[i].n/l),t[i].m/(t[i].m/l)); 78 ans[t[i].id]+=(t[i].n/l)*(t[i].m/l)*(query(r)-query(l-1)); 79 } 80 } 81 for(int i=1;i<=q;++i) print(ans[i]&0x7fffffff); 82 Ot(); 83 return 0; 84 }