zcmimi's blog
avatar
zc
2020-03-19 20:28:00
查看原题

点击跳转

\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} \sum_{x|i,x|j}\mu(x) \\ =\sum_{x=1}^n\mu(x) \left \lfloor \frac A{dx} \right \rfloor \left \lfloor \frac B{dx}\right \rfloor

avatar
zc
2020-03-19 19:22:00
查看原题

点击跳转

x分解质因数结果为x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}

f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

f(x)其实就是d(x),x的约数个数

p_1^{k_1}的约数有1,p_1,p_1^2,\cdots,p_1^{k_1}

p_2^{k_2}的约数有1,p_2,p_2^2,\cdots,p_2^{k_2}

\cdots

p_n^{k_n}的约数有1,p_n,p_n^2,\cdots,p_n^{k_n}

根据乘法原理,d(x)=(k_1+1)(k_2+1)\cdots (k_n+1)

首先可以想到的是

\sum_{i=l}^r f(i)=\sum_{i=1}^r f(i) - \sum_{i=1}^{l-1} f(i)

那么

\sum_{i=1}^n f(i) \\ =\sum_{i=1}^n \sum_{j|i}1

换个枚举顺序

=\sum_{j=1}^n \sum_{j|i}1 \\ =\sum_{j=1}^n \left \lfloor \frac nj\right \rfloor

最后数论分块就可以了

avatar
zc
2020-03-19 17:10:00
查看原题

点击跳转

首先L=\left \lceil \frac LK\right \rceil,H=\left \lceil \frac HK\right \rceil

问题转化为在[L,H]中取 N\gcd=1的数 的方案数

f_i为选出 N个不完全相同\gcd=i的数 的方案数

x[L,R]i的倍数的个数,x=\sum_{j=L}^H [i|j]=\left \lfloor \frac Hi \right \rfloor-\left \lfloor \frac Li \right \rfloor

暂时令f_i=x^N-x(所有减去完全相同的)

这时候f_i实际上是选出 N个不完全相同i|\gcd的数 的方案数

假设我们已经知道了f_{2i},f_{3i},...的最终结果

那么把f_i减去f_{2i},f_{3i},...就可以了

avatar
zc
2020-03-19 15:44:00
查看原题

点击跳转

\sum_{i=1}^n\sum_{j=1}^n lcm(A_i,A_j)

a_i = \sum_{j=1}^n [A_j=i]

那么

ans = \sum_i^n \sum_j^n a_ia_j \frac{ij}{\gcd(i,j)} \\ = \sum_{d=1}^n \frac 1d \sum_{i=1}^n \sum_{j=1}^n a_ia_j ij[\gcd(i,j)=d] \\ = \sum_{d=1}^n \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd}d \times a_{id}a_{jd}ij[\gcd(i,j)=1] \\ \text{唉,到这里我就不会了} \\ =\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij\sum_{d|i,d|j}\mu(d) \\ =\sum_{p=1}^np\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{n/dp}\sum_{j=1}^{n/dp}a_{idp}a_{jdp}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\sum_{i=1}^{n/q}\sum_{j=1}^{n/q}a_{iq}a_{jq}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\left(\sum_{i=1}^{n/q}a_{iq}i\right)^2

avatar
zc
2020-03-18 02:07:00
查看原题

点击跳转

前置知识:

  1. 杜教筛(包括狄利克雷卷积)

  2. 数论分块

  3. 欧拉函数 或 莫比乌斯函数

(会杜教筛的大佬上述都会吧)

欧拉函数卷积推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)

根据 \sum\limits_{i|n}\varphi(n)=n (1 * \varphi = Id)

= \sum_{i=1}^n\sum_{j=1}^n ij \sum_{k|i,k|j} \varphi(k)

调换枚举顺序

= \sum_{k=1}^n \varphi(k) \sum_{k|i,k|j} ij \\ = \sum_{k=1}^n \varphi(k) \sum_{k|i}i \sum_{k|j}j \\ = \sum_{k=1}^n \varphi(k) (\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}ki)^2 \\ = \sum_{k=1}^n \varphi(k) k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2

莫比乌斯函数推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j) \\ =\sum_{d=1}^n d \sum_{i=1}^n\sum_{j=1}^n ij [gcd(i,j)=d] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij [gcd(i,j)=1] \\ =\sum_{d=1}^n d^3 \sum_{i=1}^{\left \lfloor\frac nd\right\rfloor}\sum_{j=1}^{\left \lfloor\frac nd\right\rfloor} ij \sum_{k|i,k|j}\mu(k) \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) \sum_{k|i,k|j} ij \\ =\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k) k^2(\sum_{k|i}i)^2

为了方便,设sum(T)=\sum_{i=1}^T i

=\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k)k^2sum(\left \lfloor \frac n{dk}\right \rfloor)^2

T=dk

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 \sum_{d|T}d^3 \frac{T^2}{d^2}\mu(\frac Td) \\ =\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2\sum_{d|T}d\mu(\frac Td)

其中: \sum_{d|T}d\mu(\frac Td)=\varphi(T)(\mu * Id = \varphi)

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2 \varphi(T)

上述两种方法推导出的最终结果是一样的

接下来:

\sum_{k=1}^n \varphi(k)用杜教筛求出前缀和

k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2可以用数论分块求解

avatar
zc
2020-03-17 23:04:00
查看原题

点击跳转

一个点(x,y)和原点之间的点数为gcd(x,y)-1

n<m

设t=\sum_{i=1}^n \sum_{j=1}^m gcd(i,j) \\ =\sum_{d=1}^n d \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d] \\ =\sum_{d=1}^n d \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor} [gcd(i,j)=1] \\ =\sum_{d=1}^n d \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{k|gcd(i,j)}\mu(k) \\ =\sum_{d=1}^n d \sum_{k=1}^{\left \lfloor \frac nd \right \rfloor}\mu(k)\left \lfloor \frac n{dk} \right \rfloor \left \lfloor \frac m{dk} \right \rfloor \\ ans = 2*t-n*m

记得long long

avatar
zc
2020-03-17 17:16:00
查看原题

点击跳转

avatar
zc
2020-03-15 16:07:00
查看原题

点击跳转

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

avatar
zc
2020-03-15 16:05:00
查看原题

点击跳转

把题目强行转换为[POI2007]ZAP-Queries

Ans((1,b),(1,d))-Ans((1,b),(1,c-1))-Ans((1,a-1),(1,d))+Ans((1,a-1),(1,c-1))

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

avatar
zc
2020-03-15 15:48:00
查看原题

点击跳转

n<m \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_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

数论分块套数论分块会tle,继续老套路优化

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

可以先预处理出函数s(T)=\sum_{d|T}{f_d}^{\mu(\frac Td)}的前缀积

然后就可以做到数论分块O(\sqrt n)的复杂度了

25/73
Search
search