传送门:https://ac.nowcoder.com/acm/contest/10845/F
题意
$$求解ans[i]=\sum_{i=1}^n\sum_{j=1}^n\varphi (ij)\varphi [gcd(i,j)]$$
思路
前置技能:$\varphi(ij)=\frac{\varphi(i) \varphi(j)gcd(i,j)}{\varphi[gcd(i,j)]}$
根据上式得: $$\sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)gcd(i,j)$$
$$\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n\varphi (i)\varphi(j)[gcd(i,j)=k]$$
$$\sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)[gcd(i,j)=1]$$
$$\sum_{k=1}^nk\sum_{i=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\varphi (ik)\varphi(jk)\sum_{di\;dj}\mu(d)$$
交换枚举顺序:
$$\sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)\sum_{i=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)\varphi(jkd)$$
$$\sum_{k=1}^nk\sum_{d=1}^{\left \lfloor \frac{n}{k}\right \rfloor}\mu(d)[\sum_{j=1}^{\left \lfloor \frac{n}{kd}\right \rfloor}\varphi (ikd)]^2$$
令T=kd并交换枚举顺序:
$$\sum_{T=1}^{n}\sum_{kT}k\mu(\frac{T}{k})[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2$$
$由\varphi = id*\mu得:$
$$\sum_{T=1}^{n}\varphi(T)[\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT)]^2$$
$设f(n/T)=\sum_{j=1}^{\left \lfloor \frac{n}{T}\right \rfloor}\varphi (iT),则最终式为:$
$$ans[n]=\sum_{T=1}^n\varphi(T)[f(n/T)]^2$$
但是这题要求的是ans[1 - n],我们发现
$在枚举T时,n在[i*T,(i+1)*T)之间,\frac{n}{T}的值都一样,\varphi(T)[f(n/T)]^2的贡献不变。$
$所以我们在求ans[n]的过程中,对i*T做一个差分,最后在求一个前缀和即可。$
Code(445MS)
1 | ##pragma GCC optimize(2) |
本文作者:jujimeizuo
本文地址: https://blog.jujimeizuo.cn/2021/01/15/nowcoder-practice76-f/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!