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: | Read Count: 1683
Avatar_small
AP SSC General Scien 说:
2022年9月16日 02:43

All Andhra Pradesh State Class 10th (SSC) Students can download AP SSC Science model paper 2023 with Answer solutions in Chapter by Chapter for Physical Science, Chemistry, Biological Science and Environmental science for AP SSC Science Model Paper 2023 examination test for Unit Test-1, Unit Test-2, AP SSC General Science Model Paper Unit Test-3, Unit Test-4, and Quarterly, Half Yearly, Pre-Final with Annual final examination tests 2023. The Andhra Pradesh State Board of Secondary Education has published the General Science model paper with study material with practice paper with mock test question bank as AP 10th Biology, PS, Chemistry Model Paper 2023 for all examination tests conducted by BSEAP.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

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