题解 P3312 【[SDOI2014]数表】

Vocalise

2020-10-29 22:37:02

Solution

数据结构和数论结合。 考虑除了 $a$ 限制以外这个题目就是平凡的。 因此直接写出式子: $$ \begin{aligned} &\quad\sum_{i=1}^{\min}\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a] \\ &= \sum_{d=1}^{\min}\sigma(d)[\sigma(d)\le a]\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) = d] \\ &= \sum_{d=1}^{\min}\sigma(d)[\sigma(d)\le a]\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1] \\ &= \sum_{d=1}^{\min}\sigma(d)[\sigma(d)\le a]\sum_{t=1}^{\min/d}\mu(t)\lfloor\frac n{dt} \rfloor \lfloor\frac m{dt} \rfloor \\ \end{aligned} $$ 考虑此时是一个 $\mathcal O(n)$ 双重分块的式子,可以 $\mathcal O(n)$ 回答一个询问。 但是对于本题来说是不够的。 $$ \begin{aligned} &= \sum_{d=1}^{\min}\sigma(d)[\sigma(d)\le a]\sum_{d|t}^{\min}\mu(\frac td)\lfloor\frac nt \rfloor \lfloor\frac mt \rfloor \\ &= \sum_{t=1}^{\min}\lfloor\frac nt \rfloor \lfloor\frac mt \rfloor \sum_{d|t}\sigma(d)[\sigma(d)\le a]\mu(\frac td) \end{aligned} $$ 此时得到一个分块和卷积的式子。 发现卷积部分有和 $a$ 有关的因素。 如果考虑维护该卷积的前缀和的话,可以得到一个做法。 离线,对 $a$ 从小到大考虑所有询问,且对所有 $d$ 按 $\sigma (d)$ 排序。 在卷积中加入所有尚未加入的 $\sigma(d)\le a$,然后分块计算。 容易发现我们要支持单点修改,分块时区间求和。使用树状数组。 复杂度分析:树状数组部分需要加入 $\mathcal O(n\log n)$ 次,即 $\mathcal O(n\log^2n)$。 分块部分为 $\mathcal O(q\sqrt n\log n)$,因此总复杂度是 $\mathcal O(n\log^2n+q\sqrt n\log n)$。 --- 一个看似前置的问题:如何求 $\sigma$,即因数和? 根据定义其显然是积性函数,我们可以欧拉筛。 对于质数 $p$,有基本的结论: $$ \sigma(p) = 1 + p $$ $$ \sigma(p^k) = \sum_{i=0}^kp^i $$ 因此考虑 $i$ 和质数 $p$,$p$ 是 $i\times p$ 的最小质因子。 1. $p \mid i$: 此时由 $i\times p^{k-1}$ 推知 $i\times p^k$。 引入新的函数 $pw$,表示最小质因子在该数中的幂。 因此有 $$ \sigma(i\times p) = \sigma(\frac i{pw(i)})\times\sigma(pw(i)\times p) $$ 但是特别有 $i = p^k$,此时 $$ \sigma(i\times p) = \sigma(i)\times p + 1 $$ 2. $\text{otherwise}$ 此时加入新的素数,比较简单是 $$ \sigma(i\times p) = \sigma(i)\times(p + 1) $$ 而又不得不提到 $pw$ 的筛法。 加入新素数时 $pw(i\times p)$ 为 $p$,否则为 $pw(i)\times p$。 至此本题已经得到充分解决。 ```cpp #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> typedef long long ll; const int Q = 20001; const int N = 100001; const ll P = 1ll << 31; inline int read() { int x = 0, f = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); } do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9'); return x * f; } int T; struct Query { int n,m,a,id; friend bool operator <(const Query &x,const Query &y) { return x.a < y.a; } } q[Q]; int mk[N],p[N],tot; ll sgm[N],pw[N],mu[N]; int number[N]; bool cmp(int x,int y) { return sgm[x] < sgm[y]; } void Seive() { sgm[1] = pw[1] = mu[1] = 1; for(int i = 2;i < N;i++) { if(!mk[i]) { p[++tot] = i; sgm[i] = i + 1, pw[i] = i; mu[i] = P - 1; } for(int j = 1;j <= tot && p[j] * i < N;j++) { mk[i * p[j]] = true; if(i % p[j]) { pw[i * p[j]] = p[j]; sgm[i * p[j]] = sgm[i] * (p[j] + 1); mu[i * p[j]] = P - mu[i]; } else { pw[i * p[j]] = pw[i] * p[j]; if(i == pw[i]) sgm[i * p[j]] = sgm[i] * p[j] + 1; else sgm[i * p[j]] = sgm[i / pw[i]] * sgm[pw[i] * p[j]]; mu[i * p[j]] = 0; break; } } } return; } ll fen[N],Ans[N]; void Add(int x,ll v) { for(;x < N;x += x & (-x)) fen[x] = (fen[x] + v) % P; } ll Sum(int l,int r) { ll res = 0; l--; for(;r;r -= r & (-r)) res = (res + fen[r]) % P; for(;l;l -= l & (-l)) res = (res - fen[l] + P) % P; return res; } int main() { T = read(); for(int i = 1;i <= T;i++) q[i].n = read(), q[i].m = read(), q[i].a = read(); for(int i = 1;i <= T;i++) q[i].id = i; std::sort(q + 1,q + 1 + T); Seive(); for(int i = 1;i < N;i++) number[i] = i; std::sort(number + 1,number + N,cmp); int rg = 1; for(int i = 1;i <= T;i++) { while(sgm[number[rg]] <= q[i].a && rg < N) { for(int j = 1;number[rg] * j < N;j++) Add(number[rg] * j,(1ll * sgm[number[rg]] * mu[j]) % P); rg++; } ll ans = 0; for(int l = 1;l <= q[i].n && l <= q[i].m;l++) { int r = std::min(q[i].n / (q[i].n / l),q[i].m / (q[i].m / l)); ans = (ans + 1ll * Sum(l,r) * (q[i].n / l) % P * (q[i].m / l)) % P; l = r; } // std::printf("%lld\n",ans); Ans[q[i].id] = ans; } for(int i = 1;i <= T;i++) std::printf("%lld\n",Ans[i]); return 0; } ```