|
|
back to boardHow can I sol;ve this faster? My program run in 0.741 seconds and i saw most people only needed 0.09s. How can i solve this any faster? var d:array[1..50000] of integer; n,m,i,j,k:longint; begin fillchar(d,sizeof(d),0); readln(n,m); for i:=m+1 to n do begin k:=i; for j:=2 to trunc(sqrt(k)) do while k mod j=0 do begin inc(d[j]); k:=k div j; end; if k<>1 then inc(d[k]); end; for i:=1 to n-m do begin k:=i; for j:=2 to trunc(sqrt(k)) do while k mod j=0 do begin dec(d[j]); k:=k div j; end; if k<>1 then dec(d[k]); end; k:=0; for i:=2 to n do if d[i]>0 then inc(k); writeln(k); end. Re: How can I sol;ve this faster? > My program run in 0.741 seconds and i saw most people only needed > 0.09s. How can i solve this any faster? > > var d:array[1..50000] of integer; > n,m,i,j,k:longint; > begin > fillchar(d,sizeof(d),0); > readln(n,m); > for i:=m+1 to n do begin > k:=i; > for j:=2 to trunc(sqrt(k)) do > while k mod j=0 do begin > inc(d[j]); k:=k div j; > end; > if k<>1 then inc(d[k]); > end; > for i:=1 to n-m do begin > k:=i; > for j:=2 to trunc(sqrt(k)) do > while k mod j=0 do begin > dec(d[j]); k:=k div j; > end; > if k<>1 then dec(d[k]); > end; > k:=0; > for i:=2 to n do > if d[i]>0 then inc(k); > writeln(k); > end. > Re: How can I sol;ve this faster? 0.001s, 336kb. Use following fact from the number theory: Power of each prime in binomial coefficient's factorization equals to the number of borrows in the substraction n-k in base p. Iterate all primes less then N and count it if prime will greater then 0; |
|
|