Квадраты

[evgeny]

Программа, работающая за $3.5$ секунды перебирает все точки и заполняет битовую маску искомого множества.
Более быстрая версия делает то же самое, только точки рассматриваются по кольцам, в связи с этим размер массива масок уменьшается и попадает в кэш.
Ну и вместо вычисления $x^2+y^2$ каждый раз заново, т.к. следующая точка отличается от предыдущей на $1$ по одной из координат просто прибавляется изменение.

Вот код на C# (он работает менее $0.6$ секунды при $n\le 10^8$)

   uint[] bitMask = new uint[1<<22];

   int step = 1<<18;

   public int nSqr(int l1, int l2)
   {
      int i,j;
      int l3 = l2-l1;

      if ( l3 < 0) return 0;

      for(i=0;i<=l3>>5;i++)
         bitMask[i] = 0;

      int k1,k2;

      k1 = (int)math.Sqrt(l1);
      while(k1*k1<l1) k1++;

      k2 = l2;
      for(i=0;i<=k2;i++, k1--)
      {
         int s = i*i + k1*k1 - l1;
         j = k1*2+1;
         if ( s < 0 ) 
         {
            s+= j;
            j+=2;
            k1++;

         }
         for(;s<=l3;j+=2)
         {
            bitMask[s>>5] |= 1U<<(s&31);
            s += j;
         }
         k2 = j>>1;
      }
      
      int[] nbits = new int[256];
      for(i=1;i<256;i++)
         if ( i%2==0) nbits[i] = nbits[i>>1];
         else nbits[i] = nbits[i>>1]+1;

      int ans = 0;
      for(i=0;i<=(l3>>5);i++)
      {
         uint m = bitMask[i];
         ans += nbits[m&0xFF];
         m>>=8;
         ans += nbits[m&0xFF];
         m>>=8;
         ans += nbits[m&0xFF];
         m>>=8;
         ans += nbits[m];
      }
      return ans;
   }

   public int nSqr( int l)
   {
      int ans = 0;
      int i=0;
      while(i + step <= l)
      {
         ans += nSqr(i+1, i+step);
         i+=step;
      }
      ans += nSqr(i+1, l);
      return ans;

   }