BZOJ[Sdoi2014]数表 莫比乌斯反演

[Sdoi2014]数表

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 2383  Solved: 1229
[Submit][Status][Discuss]

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

Source

 http://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html

 

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<set>

 #include<ctime>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<map>

 #include<cmath>

 #define inf 1000000000

 #define pa pair<int,int>

 #define ll long long

 using namespace std;

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int Q,mx,cnt;

 struct data{

     int n,m,a,id;

 }q[];

 bool mark[];

 int pri[],mu[],t[];

 int ans[];

 pair<int,int> F[];

 bool operator<(data a,data b)

 {

     return a.a<b.a;

 }

 void add(int x,int val)

 {

     for(int i=x;i<=mx;i+=i&-i)t[i]+=val;

 }

 int query(int x)

 {

     int tmp=;

     for(int i=x;i;i-=i&-i)tmp+=t[i];

     return tmp;

 }

 void pre()

 {

     mu[]=;

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

     {

         if(!mark[i])pri[++cnt]=i,mu[i]=-;

         for(int j=;j<=cnt&&pri[j]*i<=mx;j++)

         {

             mark[pri[j]*i]=;

             if(i%pri[j]==){mu[pri[j]*i]=;break;}

             else mu[pri[j]*i]=-mu[i];

         }

     }

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

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

             F[j].first+=i;

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

 }

 void solve(int x)

 {

     int id=q[x].id,n=q[x].n,m=q[x].m;

     for(int i=,j;i<=q[x].n;i=j+)

     {

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

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

     }

 }

 int main()

 {

     Q=read();

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

     {

         q[i].n=read();q[i].m=read();q[i].a=read();q[i].id=i;

         if(q[i].n>q[i].m)swap(q[i].n,q[i].m);

         mx=max(mx,q[i].n);

     }

     pre();

     sort(q+,q+Q+);

     sort(F+,F+mx+);

     int now=;

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

     {

         while(now+<=mx&&F[now+].first<=q[i].a)

         {

             now++;

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

                 add(j,F[now].first*mu[j/F[now].second]);

         }

         solve(i);

     }

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

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

 }