[BZOJ 3529] [SDOI2014]数表

Posted on | In , | Views:

题目链接

BZOJ 3529

做法

首先令$f(i)$表示$i$的因数和，由于$n$的范围并不大，我们可以用埃氏筛方便的求出。
直接把式子列出来，要求的就是

改变一下枚举顺序，先枚举$gcd$

把$k$提出来得到

根据莫比乌斯反演的常见套路把后面带$gcd$的反演了。

再令$T=kd$

这样我们就成功做到了把$n,m$与$f(k)$分离出来了。
由于这题并不强制在线，我们先把所有询问离线下来，在将$a$从小到大枚举依次加入$看$的贡献，用树状数组维护$f(k)*\mu(\frac{T}{k})$的前缀和。再对$T$整除分块就能求得答案了。
总复杂度$O(n*log^2n+q\sqrt{n}logn)$
打个表可以知道，$n$在$10^5$范围内因数和最大为$403200$，所以树状数组的$log$实际上是$log(403200)$，最后注意读进来$a$的时候和$403200$取个$min$就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#define LL long long
#define uint unsigned int
#define N (100005)
using namespace std;
int pri,size,cnt,n,m,a,r,t; 
int mu[N],prime[N],root[N],sumu[N];
uint ans[N],f[N],T[N];
LL mod=2147483648;
bool nprime[N];
vector <int> son[N*5];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
struct query{
    int n,m,a,id;
}q[N];
inline bool cmp(query a,query b){
    return a.a<b.a;
}
inline void add(int x,uint data){
    for (int i=x;i<=size;i+=i&-i) T[i]+=data;
}
inline uint ask(int x){
    uint ret=0;
    for (int i=x;i;i-=i&-i) ret+=T[i];
    return ret;
}
int main(){
    size=100000;
    mu[1]=1;
    for (int i=2;i<=size;i++){
        if (!nprime[i]) prime[++pri]=i,mu[i]=-1;
        for (int j=1;j<=pri&&i*prime[j]<=size;j++){
            nprime[i*prime[j]]=1;
            if (i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for (int i=1;i<=size;i++){
        for (int j=1;i*j<=size;j++) f[i*j]+=i;
    }
    for (int i=1;i<=size;i++) son[f[i]].push_back(i);
    read(t);
    for (int i=1;i<=t;i++){
        read(n),read(m),read(a);
        if (n>m) swap(n,m);
        if (a>403200) a=403200;
        q[i]=(query){n,m,a,i}; 
    }
    sort(q+1,q+t+1,cmp);
    for (int i=1;i<=t;i++){
        for (int j=q[i-1].a+1;j<=q[i].a;j++){
            for (int k=0;k<son[j].size();k++){
                int t=son[j][k];
                for (int l=1;t*l<=size;l++) add(t*l,f[t]*mu[l]);
            }
        }
        for (int j=1;j<=q[i].n;){
            int r=min(q[i].n/(q[i].n/j),q[i].m/(q[i].m/j));
            ans[q[i].id]+=(ask(r)-ask(j-1))*(q[i].n/j)*(q[i].m/j);
            j=r+1;
        }
    }
    for (int i=1;i<=t;i++) printf("%u\n",ans[i]%mod);
    return 0;
}