HDU 4746 莫比乌斯反演+离线查询+树状数组

题目大意：

一个数字组成一堆素因子的乘积，如果一个数字的素因子个数（同样的素因子也要多次计数）小于等于P,那么就称这个数是P的幸运数

多次询问1<=x<=n,1<=y<=m,P , 找到多少对gcd(x,y)是P的幸运数

这里k定为k是P的幸运数

$sum_{k}sum_{x=1}^{A}sum_{y=1}^{B}[gcd(x,y)=k] = sum_{k}sum_{x=1}^{A/k}sum_{y=1}^{B/k}[gcd(x,y)=1] = sum_{k}sum_{d}mu (d)sum_{x=1}^{A/k/d}sum_{y=1}^{B/k/d}=sum_{k}sum_{d}mu (d)sum_{x=1}^{A/t}sum_{y=1}^{B/t}[t=k*d] =sum_{t}sum[t]sum_{x=1}^{A/t}sum_{y=1}^{B/t}$

这跟之前做的http://www.cnblogs.com/CSU3901130321/p/4902748.html CSU1325的题目很像，但是这里求sum[]要复杂了很多

本来是枚举k，d求sum的，但是每次询问，P都在变，而我们需要得到的是一整串的k，假定G是P最大的幸运数，那么稍微想一下就可以知道

k是在[1,G]的区间内的任何整数

那么我们将询问离线处理，按P小优先排序

那么一个个查询的时候，不断将k值更新前缀和，前缀和更新就很容易使用树状数组加速更新了，那么之后查询同样用树状数组就行了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <cmath>
  5 #include <vector>
  6 #include <algorithm>
  7 using namespace std;
  8 #define ll long long
  9 #define M 500000
 10 #define lowbit(x) x&(-x)
 11 int mu[M+5] , prime[M] , check[M+5] , tot ,  cnt[M+5];//cnt[i]记录i有多少个素因子
 12 ll f[M+5],ans[M+5];
 13 int q;
 14 vector<int> vec[M+2];
 15 
 16 void init()
 17 {
 18     for(int i=1 ; i<=M ; i++) vec[cnt[i]].push_back(i);
 19 }
 20 
 21 void get_mu()
 22 {
 23     mu[1]=1 , cnt[1]=0;
 24     for(int i=2 ; i<=M ; i++){
 25         if(!check[i]){
 26             mu[i]=-1;
 27             cnt[i]=1;
 28             prime[tot++] = i;
 29         }
 30         for(int j=0 ; j<tot ; j++){
 31             if(prime[j]*i>M) break;
 32             check[i*prime[j]] = 1;
 33             cnt[i*prime[j]] = cnt[i]+1;
 34             if(i%prime[j]==0) break;
 35             else mu[i*prime[j]] = -mu[i];
 36         }
 37     }
 38 }
 39 
 40 struct Query{
 41     int n , m , p , id;
 42     void read(int i){
 43         scanf("%d%d%d" , &n , &m , &p);
 44         id=i;
 45         if(n>m) swap(n,m);
 46     }
 47     bool operator<(const Query &m)const {
 48         return p<m.p;
 49     }
 50 }qu[M];
 51 
 52 void update(int x , int v)
 53 {
 54     for(int i=x ; i<=M ; i+=lowbit(i))
 55         f[i] = f[i]+v;
 56 }
 57 
 58 ll query(int x)
 59 {
 60     ll ans = 0;
 61     for(int i=x ; i>0 ; i-=lowbit(i)) ans = ans+f[i];
 62     return ans;
 63 }
 64 
 65 void add_mul(int x)
 66 {
 67     int len = vec[x].size();
 68     for(int i=0 ; i<len ; i++){
 69         int fac = vec[x][i];
 70         for(int d=1 ; d*fac<=M ; d++){
 71             update(d*fac , mu[d]);
 72         }
 73     }
 74 }
 75 
 76 ll cal(int n , int m)
 77 {
 78     ll ans=0;
 79     for(int t=1 , last ; t<=n ; t=last+1){
 80         last = min(n/(n/t) , m/(m/t));
 81         ans = ans+(ll)(query(last) - query(t-1))*(n/t)*(m/t);
 82     }
 83     return ans;
 84 }
 85 
 86 void solve()
 87 {
 88     int cur = 0;
 89     for(int i=1 ; i<=q ; i++){
 90         while(cur<=qu[i].p) add_mul(cur++);
 91         ans[qu[i].id] = cal(qu[i].n , qu[i].m);
 92     }
 93     for(int i=1 ; i<=q ; i++) cout<<ans[i]<<endl;
 94 }
 95 
 96 int main()
 97 {
 98    // freopen("a.in" , "r" , stdin);
 99     get_mu();
100     init();
101     scanf("%d" , &q);
102     for(int i=1 ; i<=q;  i++) qu[i].read(i);
103     sort(qu+1 , qu+q+1);
104     solve();
105     return 0;
106 }