和Leo一起做爱数学的好孩子HDU5382 GCD?LCM!-白红宇

和Leo一起做爱数学的好孩子HDU5382 GCD?LCM!

阅读量：4936 次

发布时间：2019-06-11

本文共 402 字，大约阅读时间需要 1 分钟。

超级毒瘤的反演

$F_{n}=\sum_{i=1}^{n}\sum_{j=1}^{n}\left [ LCM(i,j)+GCD(i,j)>=n \right ]$

我们发现这个外层嵌套了所以考虑递归

引理：

$[LCM(i,j)+GCD(i,j)>=n]$ 在 $(i+j)>=n+1$ 恒成立

这好理解，假设及时GCD就是较小的，那么值也是i+j

所以递归式为：

$F_{i}=F_{i-1}+2*i-1-(\sum_{i=1}^{n}\sum_{j=1}^{n}[(GCD(i,j)+LCM(i,j))==(n-1)])$

不妨：设 $T_{i}=\sum_{i=1}^{n}\sum_{j=1}^{n}[GCD(i,j)+LCM(i,j)==n]$

稍有常识的OI选手都知道

$LCM_{i,j}=\frac{i*j}{GCD_{i,j}}$

带入： $T_{i}=\sum_{i=1}^{n}\sum_{j=1}^{n}[GCD(i,j)+\frac{i*j}{GCD(i,j)}==n]$

枚举GCD

$T_{i}=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{n}[d+\frac{i*j}{d}==n]*[GCD(i,j)==d]$

交换枚举顺序

$T_{i}=\sum_{d=1}^{n}\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}[i*j*d+d==n]*[GCD(i,j)==1]$

观察右式发现d|n

减少枚举数量

$T_{i}=\sum_{d|n}^{n}\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}[i*j==\frac{n}{d}-1][GCD(i,j)==1]$

再次发现不需要枚举j

$T_{i}=\sum_{d|n}^{n}\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}[GCD(i,\frac{\frac{n}{d}-1}{i})==1]$

发现时间有三秒而这个是一个调和级数

所以埃式筛就好了

#include
    
     using namespace std;const int N=1e6+100;const int mod=258280327;int vis[N];int Prime[N];int G[N];int T[N];int F[N];int S[N];int cnt=0;void Pre(){	G[1]=1;	for(int i=2;i

转载于:https://www.cnblogs.com/Leo-JAM/p/10079099.html

你可能感兴趣的文章

06 Frequently Asked Questions (FAQ) 常见问题解答 (常见问题)