*P2398 GCD SUM[数论]
2024-09-02 15:58:43
题目描述
for i=1 to n
for j=1 to n
sum+=gcd(i,j)
解析
给出n求sum. gcd(x,y)表示x,y的最大公约数.
直接枚举复杂度为\(O(n^2)\),显然无法承受。
我们需要寻找更优的算法。
首先,打表找规律,当\(n=10\)时,是这样的
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 1 3 1 1 3 1 1 3 1
1 2 1 4 1 2 1 4 1 2
1 1 1 1 5 1 1 1 1 5
1 2 3 2 1 6 1 2 3 2
1 1 1 1 1 1 7 1 1 1
1 2 1 4 1 2 1 8 1 2
1 1 3 1 1 3 1 1 9 1
1 2 1 2 5 2 1 2 1 10
可以看到,上半部分和下半部分是对称的,我们考虑一边即可。
若\(gcd(i,j)=x\),那么\(gcd(ki,kj)=kx\)。
因此,显然对于任意\(gcd(i,j)=1\),有\(gcd(ki,kj)=k\),且充要。我们枚举\(k\),对于每个\(k\),计算\(gcd(ki,kj)=k\)的数量即可。
由于\(gcd(ki,kj),gcd(kj,ki)\)被算作分开的两次,而\(gcd(i,i)\)只会被算一次,所以减去1。
因此,对于所有的\(i\),计算
\[\sum_{i=1}^n(\sum_{k=1}^{\lfloor \frac{n}{i} \rfloor}2*\varphi(k)-1)*i
\]
\]
预处理\(\varphi(k)\)的前缀和即可\(O(n)\)求解。
推导过程
\[\begin{align}
Ans
&=\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^{n}[gcd(i,j)==k]\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k\mid i , j}[gcd(i/k,j/k)==1]\\
&=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}(2\sum_{j=1}^{i}\sum_{k=1}^n[gcd(i,j)==1]-1)\\
&=\sum_{i=1}^n(\sum_{k=1}^{\lfloor \frac{n}{i} \rfloor}2*\varphi(k)-1)*i
\end{align}
\]
Ans
&=\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^{n}[gcd(i,j)==k]\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k\mid i , j}[gcd(i/k,j/k)==1]\\
&=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}(2\sum_{j=1}^{i}\sum_{k=1}^n[gcd(i,j)==1]-1)\\
&=\sum_{i=1}^n(\sum_{k=1}^{\lfloor \frac{n}{i} \rfloor}2*\varphi(k)-1)*i
\end{align}
\]
最新文章
- 常用.NET库使用总结
- Java触发器CronTrigger
- virtualenv创建虚拟环境安装flask
- Lintcode: Binary Tree Serialization (Serialization and Deserialization Of Binary Tree)
- Redis的Set操作
- [Lua]基于cc.load('mvc') .ViewBase索引资源方案
- QT程序库
- cocos2d 高仿doodle jump 无源代码
- jquery学习之笔记一
- 浅析 Jndi / DataSource / ConnectionPool 三者
- ASP.NET Core集成现有系统认证
- JQuery 网页选项卡制作
- PBRT笔记(13)——光线传播1:表面反射
- 面向对象之反射 与__str__等内置函数
- tensorflow 源码编译
- 2019.03.25 bzoj4572: [Scoi2016]围棋(轮廓线dp)
- 【洛谷3865】 【模板】ST表(猫树)
- [django]drf知识点梳理-分页
- 用FPGA对ASIC进行原型验证的过程(转)
- ScrollView 定位