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。
sdoi2012一试第一题。
这个是poj原题。
做法很简单，枚举所有最大公约数，然后计算有多少个即可。
也就是原数除以枚举的数然后对新数求欧拉函数。
program bzoj2705;
var
tot,i:longint;
n,k,ans:int64;
p,q:array [0..32] of longint;
procedure dfs (stu:longint;now:int64);
var
i:longint;
o,k:int64;
begin
if stu>tot then
begin
k:=n div now;
o:=n div now;
for i:=2 to trunc(sqrt(k)) do
if k mod i = 0 then
begin
o:=o div i * (i-1);
while k mod i = 0 do
k:=k div i;
end;
if k>1 then
o:=o div k * (k-1);
ans:=ans+int64(o)*now;
exit;
end;
o:=1;
dfs(stu+1,now);
for i:=1 to q[stu] do
begin
o:=o*p[stu];
dfs(stu+1,now*o);
end;
end;
begin
read(n);
if n=1 then
begin
writeln(1);
exit;
end;
k:=n;
for i:=2 to trunc(sqrt(n)) do
if k mod i = 0 then
begin
inc(tot);
p[tot]:=i;
while k mod i = 0 do
begin
k:=k div i;
inc(q[tot]);
end;
end;
if k>1 then
begin
inc(tot);
p[tot]:=k;
q[tot]:=1;
end;
dfs(1,1);
writeln(ans);
end.