BZOJ

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.