BZOJ 2190：[SDOI2008]仪仗队（欧拉函数）

[SDOI2008]仪仗队

Description

　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

　　共一个数N。

Output

　　共一个数，即C君应看到的学生人数。

Sample Input

Sample Output

HINT

【数据规模和约定】　　对于 100% 的数据，1 ≤ N ≤ 40000

分析：

平面直角坐标系上的线段（且两端点为整点），其包含的整点（不包括两端点）数为gcd(|x1-x2|,|y1-y2|)-1，其中当重合时要特判。

知道上面这个这题就好做了，对于这一题，我们先要求得符合gcd(x-1,y-1) 1<=x,y<=n 的点对的个数，

产生欧拉函数表，将1~n-1的欧拉函数值加起来再乘2，相当于知道了所有2<=x,y<=n区间中能看到的点个数，然而别忘了x=1,y=1时各能看到一个点，也就是竖直方向一个，横轴方向一个，所以结果要加2，但由于统计euler表值时会将(2,2)的点对重复计算（e[1]=1，乘2后相当于多加了一次），故要减1

代码：

program asdf;

var

  e:array[..]of int64;

  n,i:longint; ans:int64;

procedure work;

var i,j:longint;

begin

  for i:= to n do e[i]:=i;

  for i:= to n do

    if e[i]=i then

     begin j:=i;

     while j<=n do begin e[j]:=e[j] div i*(i-); inc(j,i); end;

     end;

end;

begin

  readln(n);

  work;

  for i:= to n- do inc(ans,e[i]);

  writeln(ans*+);

end.

巴特西

BZOJ 2190：[SDOI2008]仪仗队（欧拉函数）

最新文章

热门文章