Kawazoe(@riverplus)さんのCodeIqの問題です。（<-2024.10.24追加）
問題はこちらにお世話になりました。解答例もあります。
->https://sw-logic.com/Portfolio/Programing/CodeIQ/3053.php
こちらにも情報があります。テストケースもこちらで見つけました。
->https://togetter.com/li/1062323
図をよく見ると気が付くのですが、螺旋というのは目くらましで、要するに、
距離mの螺旋は（出発点を加えて）m+1個の交差点のある矩形を意味します。
そこでこれは積がm+1(m<=n)になる2以上の2つの整数の組み合わせを
求める問題です。
x*y=m+1(m<=n)となるx,yをmごとに求めるのと
x*y<=n+1となるyをxごとに求めるのは同等ですので
2<=x<=sqrt(n+1)のxに対してx*y<=n+1になるy（x< y,y>x,x=y)を集めます。
あるxに対してx*y<=n+1となるyの数はdiv(n+1,x)個あります。
そのうちx>=yとなるのがx*1...x*xのx個ですので
x< yとなるyの数はdiv(n+1,x)-xです。y>xとなるyの数も同じです。
これを2<=x<=sqrt(n+1)のxについて足していきます。
x=yとなるのはxの数と同じですので最後にint(sqrt(n+1))-1を足します。
元の問題の範囲ではbigはいりません。
10^15で3-5秒くらいかかります。
ideoneがまた使えるようになっていました。
#ver 1.53, 1.73,1.10.3
function solve(n,a)
sum=big(0)
k=Int(floor(sqrt(n+1)))
for i in 2:k
sum += div(n+1,i) - i #(i^1...i^iの数を引く->x<yとなるyの数)
end
sum = sum + sum + k- 1 #(y>xとなるyの数とx=yとなるyの数を足す)
s = a == sum ? "ok " : "no "
println(s,sum)
end
solve(1,0)
solve(11,12)
solve(100,283)
solve(1000,5076)
solve(991245,11856448)
solve(1000000,11970037)
solve(1000000000,18877697665)
solve(1000000000000,25785452449093)
solve(1000000000000000,32693207724724373)
#solve(1000000000000000000,419035480966899467511)
Prologも同じ方針で書いています。
10^15で7秒以上かかります。
%:-initialization(start). %(Online Prolog Compiler,ideone.)
%start.
loop(_,1,R,R).
loop(N,E,R1,R):-
R2 is R1+div(N,E) - E,E1 is E-1,loop(N,E1,R2,R).
solve(N,R):-
N1 is N+1,E is floor(sqrt(N1)),loop(N1,E,0,R1),
R is R1*2 + E - 1.
start:-f(N,A),(solve(N,R)->(R==A->Str=" ok ";Str=" no ");
write(fail)),write(" "),write(Str),writeln(R),fail.
start.
f(1,0).
f(11,12).
f(100,283).
f(1000,5076).
f(991245,11856448).
f(1000000,11970037).
f(1000000000,18877697665).
f(1000000000000,25785452449093).
%f(1000000000000000,32693207724724373).
%f(1000000000000000000,419035480966899467511).