求n以內互質數的個數，用PASCAL寫，並且請解釋壹下

var

v:array[0..100000000]?of?boolean;

f,p,w:array[0..100000000]?of?longint;

i,j,n,k:longint;

ans:int64;

procedure?ww;

var?i,j,k:longint;

begin

fillchar(v,sizeof(v),0);

j:=0;

w[1]:=1;

for?i:=2?to?n?do

begin

?if?not?v[i]?then

begin

?inc(j);

?f[j]:=i;

p[i]:=i;

end;

?k:=1;

?while?true?do

begin

?v[f[k]*i]:=true;

?p[f[k]*i]:=f[k];

?if?i?mod?f[k]=0?then?break;

?inc(k);

?if?k>j?then?break;

?if?i*f[k]>n?then?break;

end;

?if?i?mod?(p[i]*p[i])=0?then?w[i]:=0

?else?w[i]:=w[i?div?p[i]]*(-1);

end;

end;

begin

readln(n);

ww;

ans:=0;

for?i:=1?to?n?do

ans:=ans+w[i]*(n?div?i)*(n?div?i);

writeln(ans);

end.

這是o(n)做法，空間開大點，可優化到o(n^0.5)

方法參見賈誌鵬《線性篩法》

莫比烏斯反演不懂得去cdsn或是百度上搜索

搞計算機多去cdsn,上面好多好東西

上一篇:發那科梯形圖導入不能執行

下一篇:小票打印機顯示圖形化界面怎麽弄