近期暴切的几道数学题 推导过程

· · 个人记录

P3704 [SDOI2017]数字表格

\prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \prod_{d=1}^n {f_d}^{\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]} \prod_{d=1}^n {f_d}^{\sum_{k=1}^{n/d}\mu(k)(n/kd)(m/kd)} \prod_{T=1}^n \prod_{d|T} {f_d}^{\mu(T/d)(n/T)(m/T)} \prod_{T=1}^n \left(\prod_{d|T}{f_d}^{\mu(T/d)}\right)^{(n/T)(m/T)}

P5221 Product

\prod_{i=1}^n \prod_{j=1}^n \frac{\operatorname{lcm}(i,j)}{\gcd(i,j)} \left(\prod_{i=1}^n \prod_{j=1}^n i\times j\right) \times \left(\prod_{i=1}^n \prod_{j=1}^n \gcd(i,j)\right)^{-2} \prod_{i=1}^n i^n\prod_{j=1}^n j \prod_{i=1}^n i^n\cdot n! (n!)^n\times (n!)^n=(n!)^{2n} \prod_{d=1}^n d^{\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=d]} \prod_{d=1}^n d^{\sum_{i=1}^{n/d} \sum_{j=1}^{n/d}[\gcd(i,j)=1]} \prod_{d=1}^n d^{\left(2\times \sum_{i=1}^{n/d}\phi(i)\right)-1} O(n)+O(n\log P)=O(n\log P)

CF547C Mike and Foam

\sum_{i=1}^n \sum_{j=1}^n c_ic_j[\gcd(i,j)=1] \sum_{k=1}^n \mu(k) \sum_{i=1}^{n/k} \sum_{j=1}^{n/k} c_{ik}c_{jk} \sum_{k=1}^n \mu(k) \left(\sum_{i=1}^{n/k}c_{ik}\right)^2

暴戾维护 f(k)=\sum_{i=1}^{n/k}c_{ik}=\sum_{i=1}^n [k|i]c_i

O(n)+O(n\ln n)+O(k\times q)\qquad(k\approx 200)

P1829 [国家集训队]Crash的数字表格 / JZPTAB

let\quad n\le m \sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j) \sum_{i=1}^n \sum_{j=1}^m \frac{i\times j}{\gcd(i,j)} \sum_{d=1}^n \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j] \frac{i\times j}{d} [\gcd(i/d,j/d)=1] \sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} i\times j\times d[\gcd(i,j)=1] \sum_{d=1}^n d \sum_{i=1}^{n/d} \sum_{j=1}^{m/d}i\times j[\gcd(i,j)=1] \sum_{i=1}^n \sum_{j=1}^m i\times j[\gcd(i,j)=1] \sum_{i=1}^n \sum_{j=1}^m i\times j \sum_{d|i\land d|j} \mu(d) \sum_{d=1}^n \mu(d) \sum_{i=1}^n [d|i] \sum_{j=1}^m [d|j] i\times j \sum_{d=1}^n \mu(d) \left(\sum_{i=1}^n [d|i] i\right) \left(\sum_{j=1}^m [d|j] j\right) \sum_{d=1}^n \mu(d) \times d^2\times \sum_{i=1}^{n/d} i \sum_{j=1}^{m/d} j O(n)+O(\sqrt{n}\times \sqrt{n})=O(n)

P3327 [SDOI2015]约数个数和

d(nm)=\sum_{x|n} \sum_{y|m} [\gcd(x,y)=1] \sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j} [\gcd(x,y)=1] \sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=1] \lfloor\frac{n}{x}\rfloor \lfloor\frac{m}{y}\rfloor \sum_{x=1}^n \sum_{y=1}^m \sum_{d|x\land d|y} \mu(d) \lfloor\frac{n}{x}\rfloor \lfloor\frac{m}{y}\rfloor \sum_{d=1}^n \mu(d) \sum_{x=1}^n \sum_{y=1}^m [d|x\land d|y] \lfloor\frac{n}{x}\rfloor \lfloor\frac{m}{y}\rfloor \sum_{d=1}^n \mu(d) \sum_{x=1}^{n/d} \sum_{y=1}^{m/d} \lfloor\frac{n}{dx}\rfloor \lfloor\frac{m}{dy}\rfloor \sum_{d=1}^n \mu(d) \left(\sum_{x=1}^{n/d} \lfloor\frac{n}{dx}\rfloor\right) \left(\sum_{y=1}^{m/d} \lfloor\frac{m}{dy}\rfloor\right) let\quad f(n)=\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor \sum_{d=1}^n \mu(d) \times f(n/d) \times f(m/d) O(n\sqrt{n})+O(Q\sqrt{n})

P3911 最小公倍数之和

\sum_{i=1}^n \sum_{j=1}^n \operatorname{lcm}(i,j)\times c_ic_j \sum_{i=1}^n \sum_{j=1}^n \frac{i\times j}{\gcd(i,j)} \times c_ic_j \sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} [\gcd(i,j)=1] d\times i\times j\times c_{id}\times c_{jd} \sum_{d=1}^n \sum_{k=1}^{n/d}\sum_{i=1}^{n/kd} \sum_{j=1}^{n/kd} \mu(k) \times d\times i\times j\times k^2 \times c_{idk}\times c_{jdk} let \quad T=kd \sum_{T=1}^n T\left(\sum_{i=1}^{n/T} i\times c_{iT}\right)^2 \sum_{k|T} \mu(k)\cdot k O(n\ln n)+O(n\ln n)=O(n\ln n)

P6810 「MCOI-02」Convex Hull 凸包

\sum_{i=1}^n \sum_{j=1}^m τ(i) τ(j) τ(\gcd(i,j)) \sum_{d=1}^n τ(d)\sum_{i=1}^{n/d} \sum_{j=1}^{m/d} τ(id)τ(jd)[\gcd(i,j)==1] \sum_{d=1}^n τ(d)\sum_{k=1}^{n/d}\mu(k) \sum_{i=1}^{n/dk} \sum_{j=1}^{m/dk} τ(idk) τ(jdk) let \quad T=dk \sum_{T=1}^n \sum_{i=1}^{n/T}τ(iT) \sum_{j=1}^{m/T}τ(jT) \sum_{k|T}\mu(k)τ(\frac{T}{k}) \sum_{T=1}^n \sum_{i=1}^{n/T}τ(iT) \sum_{j=1}^{m/T}τ(jT) O(n)+O(n\ln n)=O(n\ln n)

P4449 于神之怒加强版

let\quad c=k \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^c \sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} [\gcd(i,j)=1] d^c \sum_{d=1}^n \sum_{k=1}^{n/d} \mu(k) \lfloor\frac{n}{dk}\rfloor \lfloor\frac{m}{dk}\rfloor d^c \sum_{T=1}^n \lfloor\frac{n}{T}\rfloor \lfloor\frac{m}{T}\rfloor \sum_{d|T} d^c\mu(\frac{T}{d}) Fuck\; Euler \; to \; get \; f(n)=\sum_{d|n} d^c\mu(\frac{n}{d}) f(p^a)=(p^{a-1})^c\times \mu(p)+(p^a)^c\times \mu(1) =-p^{(a-1)c}+p^{ac}\qquad(a\ge 1) O(n)+O(Q\sqrt{n})

P6156 简单题

\sum_{i=1}^n \sum_{j=1}^n (i+j)^k f(\gcd(i,j)) \gcd(i,j) \sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=d](i+j)^k f(d)d \sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} [\gcd(i,j)=1](i+j)^kd^kf(d)d \sum_{d=1}^n \sum_{x=1}^{n/d} \sum_{i=1}^{n/dx} \sum_{j=1}^{n/dx} \mu(x)(i+j)^k x^k d^k f(d)d let \quad T=dx,f=\mu^2 \sum_{T=1}^n T^k \sum_{i=1}^{n/T} \sum_{j=1}^{n/T} (i+j)^k \sum_{d|T} d\times \mu^2(d)\mu(\frac{T}{d}) \sum_{T=1}^n T^k S(n/T) f(T) fuck \; Euler \; to \; get \; i^k F(n)=\sum_{i=1}^n i^k G(n)=\sum_{i=1}^n F(i) S(n)=G(2n)-2G(n) fuck \; Euler \; to \; get \; f(n)=\sum_{d|n}d\times \mu^2(d)\mu(\frac{n}{d}) f(1)=1 f(p)=1\times 1\times (-1)+p\times 1\times 1=p-1 f(p^2)=p\times 1\times (-1)=-p f(p^k)=0\quad(k\ge 3) O(n)+O(n)+O(\sqrt{n})=O(n) Sexy\; Euler

P3768 简单的数学题

\sum_{i=1}^n \sum_{j=1}^n ij\gcd(i,j) \sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{m/d} ijd^3[\gcd(i,j)=1] \sum_{d=1}^n \sum_{k=1}^{n/d} \sum_{i=1}^{n/dk} \sum_{j=1}^{n/dk} ijd^3k^2\mu(k) \sum_{d=1}^n \sum_{k=1}^{n/d} s(n/dk)^2 d^3k^2\mu(k) \sum_{T=1}^n T^2 s(n/T)^2\sum_{k|T} \mu(k)\times \frac{T}{k} \sum_{T=1}^n T^2 s(n/T)^2 \phi(T)

杜教筛

f=id^2\phi,g=id^2,h=id^3 \sum_{d|n} d^2\phi(d) \frac{n^2}{d^2}=n^2\sum_{d|n}\phi(d)=n^3 S(n)=\left(\sum_{i=1}^n h(i)\right)-\sum_{d=2}^n g(d)S(n/d) S(n)=\left(\sum_{i=1}^n i^3\right)-\sum_{d=2}^n d^2S(n/d) =\left(\sum_{i=1}^n i\right)^2-\sum_{d=2}^n d^2S(n/d) 实际是 $O(n^\frac{2}{3})$ 的，需要积分证明，感性理解