bzoj 2005 NOI 2010 能量采集

我们发现对于一个点(x,y)，与(0,0)连线上的点数是gcd(x,y)-1

那么这个点的答案就是2*gcd(x,y)-1，那么最后的答案就是所有点

的gcd值*2-n*m，那么问题转化成了求每个点的gcd值的Σ

也即：Σi<=n Σj<=m gcd(i,j)

那么首先我们知道Σphi(d) d|n=n，所以我们可以将这个式子转化成

Σi<=n Σj<=m Σ d|gcd(i,j) phi(d)

那么对于矩阵n*m来说，我们将phi(d)累加了floor(n/d)*floor(m/d)次

所以对于所有的d，答案就是Σ d<=min(n,m) floor(n/d)*floor(m/d)*phi(d)

我们可以线性筛出欧拉函数表，然后线性的求解。

/**************************************************************

    Problem:

    User: BLADEVIL

    Language: Pascal

    Result: Accepted

    Time: ms

    Memory: kb

****************************************************************/

 

//By BLADEVIL

var

    i, j                                :longint;

    prime, mindiv, phi                  :array[..] of int64;

    ans                                 :int64;

    n, m                                :int64;

     

procedure swap(var a,b:int64);

var

    c                                   :int64;

begin

    c:=a; a:=b; b:=c;

end;

 

begin

    read(n,m);

    if n>m then swap(n,m);

    phi[]:=;

    for i:= to n do

    begin

        if mindiv[i]= then

        begin

            inc(prime[]);

            prime[prime[]]:=i;

            mindiv[i]:=i;

            phi[i]:=i-;

        end;

        for j:= to prime[] do

        begin

            if i*prime[j]>m then break;

            mindiv[i*prime[j]]:=prime[j];

            if i mod prime[j]= then

            begin

                phi[i*prime[j]]:=phi[i]*prime[j];

                break;

            end else

                phi[i*prime[j]]:=phi[i]*(prime[j]-);

        end;

    end;

    for i:= to n do

        ans:=ans+(n div i)*(m div i)*phi[i];

    ans:=ans*-n*m;

    writeln(ans);

end.

巴特西

bzoj 2005 NOI 2010 能量采集

最新文章

热门文章