【传送门：】

---

简要题意：

　　给出一张数表，数表上第i行第j列的格子上的数是所有同时整除i和j的自然数的和

　　给出Q个询问，每个询问输入n,m,a，求出n*m的数表中格子上的数<=a的所有格子的和

---

题解：

　　设F(x)为x的约数和，设n<m

　　实际上就是求$\sum_{i=1}^{n}\sum_{j=1}^{m}F(gcd(i,j))[F(gcd(i,j))<=a]$

　　我们先把$F(gcd(i,j))<=a$这个限制条件省略

　　那么原始就等于$\sum_{i=1}^{n}\sum_{j=1}^{m}F(gcd(i,j))$

　　先枚举d=gcd(i,j)，得到$$\sum_{d=1}^{n}F(d)*\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}{\frac{m}{d}}[gcd(i,j)==1]$$

　　设G(x)为gcd(i,j)%x==0的数对数，f(x)为gcd(i,j)==x的数对数，显然$G(n)=\sum_{n|d}f(d)$，根据反演公式得到$f(n)=\sum_{n|d}\mu(\frac{d}{n})G(d)$

　　因为$G(x)=\frac{n}{x}*\frac{m}{x}$，所以原式等于$$\sum_{d=1}^{n}F(d)*\sum_{d|i}\mu(\frac{i}{d})*\frac{n}{i}*\frac{m}{i}$$

　　先枚举i，得到$$\sum_{i=1}^{n}\frac{n}{i}*\frac{m}{i}*\sum_{d|i}F(d)*\mu(\frac{i}{d})$$

　　然后呢，再加入限制条件，因为实际上只有当F(i)<=a时，i才能取，那么我们先预处理F，然后让F的值从小到大排序，将询问按照a的值从小到大排序

　　设$D(d)=\sum_{i|d}F(i)*\mu(\frac{d}{i})$，对于一个新进来的i，如果F(i)<=a，则将所有i|d的D(d)全部加上$F(i)*\mu(\frac{d}{i})$，可以用树状数组维护前缀和就行了

　　PS:不要用long long，不要%，%太慢了会超时，直接溢出，然后将答案&0x7fffffff

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int miu[110000],prime[110000],v[110000];struct F{    int t,d;}f[110000];bool cmpf(F n1,F n2){
   return n1.d
          
           v[i]||prime[j]>n/i) break; v[i*prime[j]]=prime[j]; if(i%prime[j]==0) miu[i*prime[j]]=0; else miu[i*prime[j]]=-miu[i]; } } for(int i=1;i<=n;i++) { f[i].t=i; for(int j=i;j<=n;j+=i) f[j].d+=i; }}struct query{ int n,m,a,id;}q[21000];bool cmp(query n1,query n2){ return n1.a
           
            q[i].m) swap(q[i].n,q[i].m); mn=max(q[i].n,mn); } sort(q+1,q+Q+1,cmp);sort(f+1,f+mn+1,cmpf); memset(a,0,sizeof(a)); for(int i=1,j=0;i<=Q;i++) { while(j+1<=mn&&f[j+1].d<=q[i].a) { j++; for(int k=f[j].t;k<=mn;k+=f[j].t) change(k,f[j].d*miu[k/f[j].t]); } getd(i); } for(int i=1;i<=Q;i++) printf("%d\n",ans[i]&0x7fffffff); return 0;}