*iroi*

mechairoi の Blog

Problem64

use warnings;
use strict;

my $ans=0;
for(1..10000) {
   $ans++ if (f($_) % 2 == 1);
}
print $ans;

sub f {
  my $N = shift;
  return rec($N, 1, - int(sqrt($N)), 1, {});
}

sub rec {
  no warnings 'recursion';
  my ($N, $k, $l, $m, $ht) = @_;

  my $n_m = ($N - $l**2) / $m;
  return 0 if $n_m == 0;
  my $a   = int((sqrt($N) - $l) / $n_m);
  my $n_l = - $l - $n_m * $a;

  return $k - $ht->{$n_l}{$n_m} if $ht->{$n_l}{$n_m};
  $ht->{$n_l}{$n_m} = $k;
  rec($N, $k+1, $n_l, $n_m, $ht);
}