bzoj 3529 数表 莫比乌斯反演+树状数组

题目大意：

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

http://wenku.baidu.com/link?url=1zHluup-GXHdByoQXhMRwRu22Uu15y4DztIr1_hKVxjHJmuLQF4_01UQhLEOR7RJIpsGyfD_5fXrx9DE7sY6JeukaNUY83In097GjUOmZ7K

ppt课件中讲的很仔细了

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100000

 #define ll long long

 #define lowbit(x) x&(-x)

 typedef pair<int , int> pii;

 int sum[N+] , mu[N+] , prime[N+] , tot;

 bool check[N+];

 pii f[N+];

 void get_mu()

 {

     mu[] = ;

     for(int i= ; i<=N ; i++) f[i].first= , f[i].second = i;

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

         if(!check[i]){

             mu[i] = -;

             prime[tot++] = i;

         }

         for(int j= ; j<tot ; j++){

             if((ll)prime[j]*i>N) break;

             check[i*prime[j]] = true;

             if(i%prime[j]){

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

             }else break;

         }

     }

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

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

             f[j].first += i;

 }

 struct Query{

     int n , m , a , id;

     void in(int i){scanf("%d%d%d" , &n , &m , &a) ; id=i;}

     void reset(){if(n>m) swap(n,m);}

     bool operator<(const Query &m)const {

         return a<m.a;

     }

 }qu[N];

 int mxl , Q , ans[N];

 void add(int x , int v)

 {

     for(int i=x ; i<=mxl ; i+=lowbit(i)) sum[i]+=v;

 }

 int query(int x)

 {

     int ret = ;

     for(int i=x ; i> ; i-=lowbit(i)) ret += sum[i];

     return ret;

 }

 int find(int n , int m)

 {

     int ret =  , last;

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

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

         ret += n/i*(m/i)*(query(last)-query(i-));

       //  cout<<n<<" "<<m<<" "<<ret<<" "<<query(last)<<" "<<query(i-1)<<endl;

     }

     return ret&(0x7fffffff);

 }

 void solve()

 {

     memset(sum ,  , sizeof(sum));

     int index =  , cnt=;

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

         while(f[index].first<=qu[i].a&&cnt<mxl){

             for(int j=f[index].second , k= ; j<=mxl ; j+=f[index].second ,k++){

                // cout<<index<<" "<<f[index].second<< " "<<f[index].first<<" "<<k<<" "<<mu[k]<<endl;

                 add(j , f[index].first*mu[k]);

             }

             index++;

             if(f[index].second<=mxl) cnt++;

         }

         ans[qu[i].id] = find(qu[i].n , qu[i].m);

     }

     for(int i= ; i<=Q ; i++) printf("%d\n" , ans[i]);

 }

 int main()

 {

     //freopen("in.txt" , "r" , stdin);

     get_mu();

     sort(f+ , f+N+);

     while(~scanf("%d" , &Q)){

         mxl = ;

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

             qu[i].in(i) , qu[i].reset();

             mxl = max(mxl , qu[i].n);

         }

         sort(qu+ , qu+Q+);

         solve();

     }

     return ;

 }