bzoj 2705 数学 欧拉函数

首先因为N很大，我们几乎不能筛任何东西

那么考虑设s(p)为 gcd(i,n)=p 的个数，显然p|n的时候才有意义

因为i与n的gcd肯定是n的因数，所以那么可得ans=Σ(p*s(p))

那么对于s(p),我们有gcd(i,n)=p即gcd(i/p,n/p)=1，也即phi(n/p)

所以枚举因数求phi就好了

/**************************************************************
    Problem: 2705
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:12 ms
    Memory:228 kb
****************************************************************/
 
//By BLADEVIL
var
    n                           :longint;
    i                           :longint;
    pi                          :array[0..510] of longint;
    cur                         :longint;
    ans                         :int64;
     
function phi(x:longint):longint;
var
    i                           :longint;
begin
    cur:=x;
    phi:=x;
    for i:=2 to trunc(sqrt(x)) do
    begin
        if cur mod i=0 then
        begin
            phi:=(phi div i)*(i-1);
            while cur mod i=0 do cur:=cur div i;
            if cur=1 then break;
        end;
        if cur=1 then break;
    end;
    if cur<>1 then phi:=(phi div cur)*(cur-1);
end;
     
begin
    read(n);
    for i:=1 to trunc(sqrt(n)) do
    begin
        if n mod i=0 then
        begin
            inc(pi[0]);
            pi[pi[0]]:=i;
            if n div i<>i then
            begin
                inc(pi[0]);
                pi[pi[0]]:=n div i;
            end;
        end;
    end;
    ans:=0;
    for i:=1 to pi[0] do
        ans:=ans+int64(pi[i]*phi(n div pi[i]));
    writeln(ans);
end.