GCD?LCM!
题意
哈哈哈哈哈懵逼钨丝做的我一本满足，爽歪歪，推公式好塔马有趣儿
咳咳，题目是：
$$
F(n)=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)\ge n]
$$
$$
S(n)=\sum_{i=1}^nF(n)
$$
t组，每组给你一个n，求S(n)。
t<=1e5,n<=1e6
思路
$$
F(n)=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)\ge n]
$$
$$
=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)\ge n-1]-\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)==n-1]
$$
由于对于后半部分来说，i，j=n时显然不符合，因此可直接降为n-1
$$
=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)\ge n-1]-\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[lcm(i,j)+gcd(i,j)==n-1]
$$将前半部分转化成F(n-1)，故修改i，j的上限，而i，j=n时一定满足要求，因此要补上2n-1
$$
=\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[lcm(i,j)+gcd(i,j)\ge n-1]+(2n-1)-\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[lcm(i,j)+gcd(i,j)==n-1]
$$
$$
=F(n-1)+(2n-1)-\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[lcm(i,j)+gcd(i,j)==n-1]
$$
令后半部分为T(n-1),则：
$$
F(n)=F(n-1)+(2n-1)-T(n-1)
$$
接下来分析T(n)
$$
T(n)=\sum_{i=1}^n\sum_{j=1}^n[lcm(i,j)+gcd(i,j)==n]
$$
令d=gcd(i,j)，又由于lcm(i,j)=ij*(gcd(i,j))，令i=id，j=jd
$$
=\sum_{d|n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}
[ijd+d==n][gcd(i,j)==1]
$$
$$
=\sum_{d|n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}
[j=\frac{\frac{n}{d}-1}{i}][gcd(i,j)==1]
$$
$$
=\sum_{d|n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}
[gcd(i,\frac{\frac{n}{d}-1}{i})==1]
$$
由于$\ i = \frac{n}{d}$ 时，条件显然不成立，因此修改i的上限
$$
=\sum_{d|n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor-1}
[gcd(i,\frac{\frac{n}{d}-1}{i})==1]
$$
令后半部分为$ G(\frac{n}{d}-1) $
$$
T(n)=\sum_{d|n}G(\frac{n}{d}-1)
$$
接下来分析G(n)
$$
G(n)=\sum_{i=1}^n[gcd(i,\frac{n}{i})==1]
$$
要满足后半部分，我们打表（或者根据思考（？？？））发现
$$
G(n)=2^k,k为n的质因子个数
$$
那么到这里，基本上要推的就都推完了，
差一个总和。
由于：
$$
F(n)=F(n-1)+(2n-1)-T(n-1)
$$
$$
=F(n-2)+(2(n-1)-1)-T(n-2)+(2n-1)-T(n-1)
$$
$$
=F(n-3)+(2(n-2)-1)-T(n-3)+(2(n-1)-1)-T(n-2)+(2n-1)-T(n-1)
$$
$$
……
$$
$$
=F(1)+\sum_{i=1}^n(2i-1)-\sum_{i=0}^{n-1}T(i)
$$
故：
$$
S(n)=\sum_{i=1}^n(F(1)+\sum_{j=1}^i(2j-1)-\sum_{j=0}^{i-1}T(j))
$$
$$
S(n)=nF(1)+\sum_{i=1}^ni^2-\sum_{i=1}^n\sum_{j=0}^{i-1}T(i)
$$
$$
=n+\frac{n(n+1)(2n+1)}{6}-\sum_{i=1}^n\sum_{j=0}^{i-1}T(i)
$$
我们一步一步来：
- 预处理，先筛出所有质数，然后是1~1e6的质因子个数，然后求得G(n)，再求得T(n)，然后对T(n)求一次前缀和得到每个sum[i]，再对每个sum[i]求前缀和ans[i]=sum[i-1]+ans[i-1]。
- 没有2了，对于每个输入的n直接用刚刚最后那个公式带进去算就好了：
$$
S(n)=n+\frac{n(n+1)(2n+1)}{6}-ans[n]
$$
哦，别忘了取模。
看！代码
1 |
|