【bzoj2705】[SDOI2012]Longge的问题

2014年6月15日3,6740

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。

题解

题目中要求出∑gcd(i,N)(1<=i<=N)。

枚举n的约数k,令s(k)为满足gcd(m,n)=k,(1<=m<=n)m的个数,则ans=sigma(k*s(k)) (k为n的约数)

因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)

phi可以在根号的时间内求出