bzoj 3529 [Sdoi2014]数表（莫比乌斯反演+BIT）

Description

有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为
能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。

Input

输入包含多组数据。
    输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

Output

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

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148

HINT

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

【思路】

　　UPD：求a只和F(1..a)有关系改为：求a只和F(i)<=a的项有关系

　　自然溢出，最后and 2^31-1

【代码】

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = 1e5+;

 struct Node {

     int n,m,a,id;

     bool operator< (const Node& rhs) const{

         return a<rhs.a;

     }

 };

 struct Fnode{

     int num,id;

     bool operator<(const Fnode& rhs) const{

         return num<rhs.num;

     }

 };

 int mx,n,m,a;

 int mu[N],su[N],sz,np[N],C[N],ans[N];

 Node que[N]; Fnode F[N];

 void add(int x,int v)

 {

     for(;x<=mx;x+=x&-x) C[x]+=v;

 }

 int query(int x)

 {

     int res=;

     for(;x;x-=x&-x) res+=C[x];

     return res;

 }

 void get_mu()

 {

     int i,j;

     mu[]=;

     for(i=;i<=mx;i++) {

         if(!np[i])

             mu[i]=-,su[++sz]=i;

         for(j=;j<=sz&&i*su[j]<=mx;j++) {

             np[i*su[j]]=;

             if(i%su[j]==)

                 mu[i*su[j]]=;

             else

                 mu[i*su[j]]=-mu[i];

         }

     }

 }

 void get_F()

 {

     int i,j;

     for(i=;i<=mx;i++) {

         for(j=i;j<=mx;j+=i)

             F[j].num+=i;

     }

     for(i=;i<=mx;i++) F[i].id=i;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

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

         scanf("%d%d%d",&n,&m,&a);

         if(n>m) swap(n,m);

         que[i]=(Node){n,m,a,i};

         mx=max(mx,n);

     }

     get_mu(); get_F();

     sort(que+,que+T+);

     sort(F+,F+mx+);

     int now=;

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

         while(now+<=mx&&F[now+].num<=que[i].a) {

             now++;

             for(int j=F[now].id;j<=mx;j+=F[now].id)

                 add(j,F[now].num*mu[j/F[now].id]);

         }

         int id=que[i].id,last; n=que[i].n,m=que[i].m;

         for(int j=;j<=n;j=last+) {

             last=min(n/(n/j),m/(m/j));

             ans[id]+=(query(last)-query(j-))*(n/j)*(m/j);

         }

     }

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

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

     return ;

 }