Матч 17, Биквадратные суммы (BisquareSums)

Число b называется биквадратным, если существуют (возможно равные) такие целые числа x и y, что x² + y² = b. По заданным числам low и high вычислить количество биквадратных чисел на отрезке [low; high].

Класс: BisquareSums

Метод: int getSums(int low, int high)

Ограничения: 1 £ low £ 100, low £ high £ 100.

Вход. Два целых числа low и high.

Выход. Количество биквадратных чисел на отрезке [low; high].

Пример входа

low	high
1	5
7	7
56	99

Пример выхода

4

0

16

РЕШЕНИЕ

перебор

Обнулим массив m длины 101. Переберем все возможные значения i и j от 0 до 100 и присвоим m[i*i + j*j] = 1. Таким образом, число b является биквадратным, если m[b] = 1. Просматриваем ячейки массива m от low до high и подсчитываем в переменной s количество таких, которые содержат в себе 1.

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

int m[101];

class BisquareSums

{

public:

int getSums(int low, int high)

{

int i, j, s;

memset(m,0,sizeof(m));

for(i = 0; i < 10; i++)

for(j = 0; j < 10; j++)

if (i*i + j*j <= 100) m[i*i+j*j] = 1;

for(s = 0,i = low; i <= high; i++) if (m[i]) s++;

return s;

}

};