bzoj2705

maksyuki 发表于 oj 分类,标签:
0

2705: [SDOI2012]Longge的问题

Description

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

Input

一个整数,为N。

Output

一个整数,为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据,0<N<=2^16。

对于100%的数据,0<N<=2^32。

Source

round1 day1

 

题目类型:欧拉函数

算法分析:枚举N所有的约数x,则如果知道gcd(i, N) = x(1 <= i <= N)的个数,直接将其乘以x累加起来就是答案。而gcd (i, N) = x可以转换为gcd (i / x, N / x) = 1,而后者的个数可以由欧拉函数求解得到。注意本问题不需要枚举所有的约数,只需要枚举所有小于等于sqrt(N)的约数即可,因为大于sqrt (N)的约数可以由小于sqrt(N)的约数计算得到,这样时间复杂度就是O(sqrt (N))的