10
21
2013
1

【BZOJ2190】【SDOI2008】仪仗队【欧拉函数】

线性筛一下欧拉函数,然后加起来×2加3即可。

program p2190;
	var
		x:array[1..400000] of boolean;
		prime,phi:array[1..400000] of longint;
		len,n,i,j,tot:longint;
	begin
		readln(n);
		dec(n);
		fillchar(x,sizeof(x),false);
		len:=0;
		for i:=2 to n do begin
			if x[i]=false then begin
				inc(len);
				phi[i]:=i-1;
				prime[len]:=i;
			end;
			j:=1;
			while (j<=len) and (prime[j]*i<=n) do begin
				x[i*prime[j]]:=true;
				if i mod prime[j]=0 then begin
					phi[prime[j]*i]:=phi[i]*prime[j]; break;
				end else
					phi[prime[j]*i]:=phi[i]*(prime[j]-1); 
				inc(j);
			end;
		end;
		tot:=0;
		for i:=1 to n do
			tot:=tot+phi[i];
		tot:=tot*2+3;
		writeln(tot);
	end.
Category: 欧拉函数 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com