BZOJ 2705

SDOI真有人性,出这么欢乐题 –root

枚举$n$的约数$k$,令$s(k)$为满足$gcd(m,n)=k,(1{\leq}m{\leq}n)m$的个数,则$ans=\sum_{n\ mod\ k=0}(k*s(k))$

${\because}\ gcd(m,n)=k$

${\therefore}\ gcd(\frac{m}{k},\frac{n}{k})=1$

${\therefore}\ s(k)=\varphi(\frac{n}{k})$

其实主要在于如何$O(\sqrt{n})$的复杂度求单个$\varphi(x)$ 步骤如下:

  1. 将$\varphi$赋为$x$,表示当前与$x$互质的数有$x$个

  2. 找到一个$x$的约数$k$

  3. 找到了约数,那么和$x$互质的数就又少了$\frac{\varphi}{k}$个,$\varphi=\varphi*\frac{k-1}{k}$

  4. 将这个约数从$x$中全都除掉

  5. 重复以上步骤直到找不到$x$的约数

  6. 最后如果$x$是质数还要特判一下

  7. 返回$\varphi$的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
program bzoj_2705;
var n,ans:int64;
m,i:longint;
function phi(x:longint):longint;
var i:longint;
begin
phi:=x;
for i:=2 to trunc(sqrt(x)) do
if x mod i=0 then
begin
phi:=phi div i*(i-1);
while x mod i=0 do x:=x div i;
end;
if x>1 then phi:=phi div x*(x-1);
end;
begin
readln(n);
m:=trunc(sqrt(n));
ans:=0;
for i:=1 to m do
if n mod i=0 then
begin
inc(ans,i*phi(n div i));
inc(ans,(n div i)*phi(i));
end;
if int64(m)*int64(m)=n then dec(ans,(n div m)*phi(m));
writeln(ans);
end.