Description

有一张 n×m 的数表，其第 i 行第 j 列（1 <= i <= n, 1 <= j <= m）的数值为

能同时整除 i 和 j 的所有自然数之和。给定 a , 计算数表中不大于 a 的数之和。

Input

输入包含多组数据。

输入的第一行一个整数Q表示测试点内的数据组数

接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

1 < =N．m < =10^5 ， 1 < =Q < =2×10^4

Output

对每组数据，输出一行一个整数，表示答案模2^31的值。

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148

解题思路：

这道题就是让我们求${\sum_{i=1}^{N}}{\sum_{j=1}^{M}}{\sigma(gcd(i,j))}({\sigma(gcd(i,j))}<=a)$

a比较让人恶心，考虑将${\sigma(gcd(i,j))}$按次序加入答案，直接统计，就是一种离线的做法。

那么就不需要考虑a了，答案就变成了(设n<=m)

${\sum_{i=1}^{n}}{\sum_{j=1}^{m}}{\sigma(gcd(i,j))}$

$={\sum_{d=1}^{n}}{\sigma(d)}{\sum_{d|i}}{n}{\sum_{d|j}^{m}}[gcd(i,j)==d]$

$={\sum_{d=1}^{n}}{\sigma(d)}{\sum_{i=1}^{\left \lfloor {\frac{n}{d}} \right \rfloor}}{\sum_{j=1}^{\left \lfloor {\frac{n}{d}} \right \rfloor}}{[gcd(i,j)==1]}$

$={\sum_{d=1}^{n}}{\sigma(d)}{\sum_{k=1}^{\left \lfloor {\frac{n}{d}} \right \rfloor}}{\mu(k)}{\left \lfloor {\frac{n}{dk}} \right \rfloor}{\left \lfloor {\frac{m}{dk}} \right \rfloor}$

设T=dk

$={\sum_{T=1}^{n}}{\sum_{d|T}}{\sigma(d)}{\mu(\frac{T}{d})}{\left \lfloor {\frac{n}{T}} \right \rfloor}{\left \lfloor \frac{m}{T} \right \rfloor}$

按顺序加入${\sigma(d)}$就好了

由于具有循环性质，在倍数位置加上就好了

取模卡我好长时间，没想到是这种方法。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 typedef long long lnt;

 const int N=;

 struct int_2{int a,b;bool friend operator < (int_2 x,int_2 y){if(x.a!=y.a)return x.a<y.a;return x.b<y.b;}}F[N];

 int prime[N];

 int miu[N];

 bool vis[N];

 int cnt;

 int line[N];

 struct qust{

     int n,m,a;

     int no;

     int ans;

 }q[N];

 int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int pos,int v)

 {

     while(pos<N)

     {

         line[pos]+=v;

         pos+=lowbit(pos);

     }

     return ;

 }

 int query(int pos)

 {

     int ans=;

     while(pos)

     {

         ans+=line[pos];

         pos-=lowbit(pos);

     }

     return ans;

 }

 void gtp(void)

 {

     miu[]=;

     for(int i=;i<N;i++)

     {

         if(!vis[i])

         {

             prime[++cnt]=i;

             miu[i]=-;

         }

         for(int j=;j<=cnt&&prime[j]*i<N;j++)

         {

             int x=i*prime[j];

             vis[x]=true;

             if(i%prime[j]==)

             {

                 miu[x]=;

                 break;

             }

             miu[x]=-miu[i];

         }

     }

     for(int i=;i<N;i++)

     {

         for(int j=i;j<N;j+=i)

             F[j].a+=i;

         F[i].b=i;

     }

     return ;

 }

 bool cmp(qust x,qust y)

 {

     return x.a<y.a;

 }

 bool cmq(qust x,qust y)

 {

     return x.no<y.no;

 }

 int main()

 {

     gtp();

     int T;

     scanf("%d",&T);

     for(int i=;i<=T;i++)

     {

         scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a);

         q[i].no=i;

     }

     std::sort(q+,q+T+,cmp);

     std::sort(F+,F+N);

     for(int i=,j=;i<=T;i++)

     {

         for(;j<N&&F[j].a<=q[i].a;j++)

         {

             for(int k=F[j].b;k<N;k+=F[j].b)

                 update(k,F[j].a*miu[k/F[j].b]);

         }

         int n=q[i].n,m=q[i].m;

         if(n>m)

             std::swap(n,m);

         for(int u=,v;u<=n;u=v+)

         {

             v=std::min(n/(n/u),m/(m/u));

             q[i].ans+=(query(v)-query(u-))*(n/u)*(m/u);

         }

     }

     std::sort(q+,q+T+,cmq);

     for(int i=;i<=T;i++)

         printf("%d\n",q[i].ans&(0x7fffffff));

     return ;

 }

巴特西

BZOJ3529: [Sdoi2014]数表(莫比乌斯反演，离线)