bzoj3529: [Sdoi2014]数表

莫比乌斯反演

---

题目链接

bzoj3529: [Sdoi2014]数表

题解

另$d(x)$表示$x$的约束和
就是求这个

$$\sum_{i = 1}^n\sum_{j = 1}^{m} d(gcd(i,j)) \leq a$$
首先，我们不考虑a
另$f(x)=\sum_i^n\sum_j^m gcd(i,j) == x$
那么$f(x) = \sum_{x|p}\mu(\frac{p}{x})\lfloor \frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor$
则答案就是
$$\sum_x^{min(n,m)}f(x)d(x)$$
$$=\sum_x^{min(n,m)}d(x)\sum_{x|p} \mu(\frac{p}{x})\lfloor \frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor$$
$$\sum_p^{min(n,m)}\lfloor \frac{n}{p}\rfloor\lfloor\frac{m}{p}\rfloor \sum_{x|p}\mu(\frac{p}{x})f(x)$$
对于$f()$我们可以nlogn筛出来
考虑a的限制，我们可以离线做
对于$\sum_{x|p}\mu(\frac{p}{x})f(x)$这部分
对于询问a的排序，对于$f(i)$排序，对于每次询问，把$f(i)\leq a$的每个$i$按上式丢到一个bit里维护一下前缀和
复杂度$O(\sqrt {n} logn + nlog^2n)$

代码

#include <queue> 
#include <cstdio> 
#include <algorithm> 
inline int read() { 
    int x = 0; 
    char c = getchar(); 
    while(c < '0' || c > '9')c = getchar();  
    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar();
    return x; 
} 
const int mod = (1 << 31); 
const int maxn = 100007; 
int p[maxn],mu[maxn],mx; bool vis[maxn]; 
struct node { 
    int n,m,a,id; 
    bool operator < (const node & k)const { 
        return a < k.a; 
    } 
} q[maxn]; 
std::pair<int,int>F[maxn]; 
void getmu() { 
    int size = mx,num = 0; 
    mu[1] = 1; 
    for(int i = 2;i <= size;++ i) { 
        if(!vis[i]) p[++ num] = i,mu[i] = -1; 
        for(int j = 1;j <= num && i * p[j] <= size;++ j) {  
            vis[i * p[j]] = true; 
            if(i % p[j] == 0) { 
                mu[i * p[j]] = 0; break; 
            } mu[i * p[j]] = -mu[i];  
        } 
    } 
    for(int i = 1;i <= size;++ i) 
        for(int j = i;j <= size;j += i) 
            F[j].first += i; 
    for(int i = 1;i <= size;++ i)F[i].second = i; 
} 
int ans[maxn]; 
#define lowbit(x) x&(-x)
int bit[maxn << 1]; 
void add(int x,int num) { 
    for(int i = x;i <= mx; i += lowbit(i))bit[i] += num; 
} 
int query(int x) { 
    int ret = 0; 
    for(int i = x;i; i -= lowbit(i)) ret += bit[i]; 
    return ret; 
} 
void solve(int x) { 
    int n = q[x].n,m = q[x].m; 
    for(int i = 1,j;i <= q[x].n;i = j + 1) { 
        j = std::min(m / (m / i),n / (n/i)); 
        ans[q[x].id] += (n / i) * (m / i) * (query(j) - query(i - 1)); 
    } 
} 
int main() { 
    int k = read(); 
    for(int i = 1;i <= k;++ i) { 
        q[i].n = read(),q[i].m = read(),q[i].a = read(); 
        if(q[i].n > q[i].m) std::swap(q[i].n,q[i].m); 
        q[i].id = i; mx = std::max(mx,q[i].n); 
    } 
    getmu(); 
    std::sort(q + 1,q + k + 1); 
    std::sort(F + 1,F + mx + 1); 
    for(int i = 1,now = 0;i <= k;++ i) { 
        for(;now + 1 <= mx && F[now + 1].first <= q[i].a;) { 
            now ++; 
            for(int j = F[now].second;j <= mx;j += F[now].second) { 
                //printf("%d\n",now); 
                add(j,F[now].first * mu[j / F[now].second]); 
            } 
        } 
        solve(i); 
    } 
    //printf("%d\n",mod); 
    for(int i = 1;i <= k;++ i) { 
        printf("%d\n",ans[i] & 0x7fffffff ); 
    } 
    return 0; 
}