Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

12/6
15:25
欧拉函数

SDOI2012 Longge的问题 [bzoj 2705]

00:00/00:00

d439b6003af33a87537c95f2c55c10385243b5c1  fbec0e3fb80e7bec9527fa302d2eb93899506b54

♦♦♦♦♦♦   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的约数x,令s(k)为1-n中与n的最大公约数为k的个数,则ans=sigma(k*s(k)) 。因为gcd(m,n)=k,所以gcd(m/k,n/k)=1,于是s(k)=euler(n/k)。

c++:

pascal:

 

 

SDOI2012 Longge的问题 [bzoj 2705]