题目链接:https://www.spoj.pl/problems/LCMSUM/
SPOJ Problem Set (classical)
5971. LCM Sum
Problem code: LCMSUM
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Example
Sample Input :
3
1
2
5
Sample Output :
1
4
55
Constraints
1 <= T <= 300000
1 <= n <= 1000000
这个题目如果用读数优化,可能时间会更快点,不过我没有改了。。
我的代码花了4.27s,可以说是卡过去的。。
这个题,个人感觉非常不错。应该是POJ 2480 gcd sum的升级版。
说一下做法吧。
我最先开始已经推导出:ans=sigma(n/d*eular(n/d)*n/2)
n/2是每一个与n的最大公约数为d的数的平均数。(理论依据是所有小于n的且与n互质的数的和为(1+2+3+..+n)/2,详细内容可以查阅相关资料)
然后说说这个式子怎么转化吧。
其实,n/d*eular(n/d)=d*eular(d)。原因就是d会出现的数字,n/d也一定会出现。
举个例子:n=6,那么d=1,2,3,6 n/d=6,3,2,1
完全一样的说~
然后于是ans=sigma(d*eular(d)*n/2)
这里说说当d=1的时候,这个时候是一个特殊情况。
因为我们这个时候平均数事实上是n,而非n/2
所以式子需要修正:ans=sigma(d*eular(d)*n/2+n/2)
ans=n*sigma(d*eular(d)+1)
注意到上面两个式子在数学上面并不相等,但是由于这里,除号是一个整除法,所以这里,其实两个式子是相等的(至少计算机算出来是一样的)
下面就是我的代码了:
分享到:
相关推荐
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ-Solutions:SPOJ算法问题的解决方案
My solution for some spoj problems
cp:一些SPOJ问题的解决方案
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
SPOJ( )上选定问题的解决方案
联系 Python中SPOJ问题的解决方案。
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
spoj MSTS kruskal +生成树
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
gcd(a,b)= d (d为素数,1,1)