[POJ2480/Luogu2303/BZOJ2705] [SDOI2012]Longge的问题(欧拉函数)

发布于 2018-01-17  177 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[POJ2480/Luogu2303/BZOJ2705] [SDOI2012]Longge的问题(欧拉函数)

Description

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。

Http

POJ
BZOJ
Luogu

Tag

欧拉函数

题目大意

求\[\sum_{i=1}^{n} gcd(i,n)\]

解决思路

这一题类似,设\(n=a*b\),那么若有\(gcd(a*b,a*c)==a\),则\(gcd(b,c)==1\),那么题目变成求\(\phi(n/a)\)。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[POJ2480/Luogu2303/BZOJ2705] [SDOI2012]Longge的问题(欧拉函数)


HNCJ OIer