Как ускорить алгоритм?
Сначала учитываем 3*N^2 треугольников, у которых вершина с прямым углом лежит на одной из координатных осей (или вообще в точке (0,0)). 
Теперь посчитаем все остальные треугольники.
Пусть (a,b) - координаты вершины с прямым углом, 0 < a <= N, 0 < b <= N.
Если c=НОД(a,b), a1=a/c, b1=b/c, то оставшаяся вершина должна иметь координаты (x,y)=(a+t*b1,b-t*a1), где t - ненулевое целое число. 
Должны выполняться условия 0 <= x,y <= N. Перепишем их в виде условий на t:
-a/b1 <= t <= (N-a)/b1, -(N-b)/a1 <= t <= b/a1 (заметим, что a1, b1 больше нуля, так что делить можно). Учитывая, что t должно быть целым, оно лежит на отрезке от 
t0 = -floor(min(a/b1,(N-b)/a1)) 
до
t1 = floor(min((N-a)/b1,b/a1))
И, поскольку запрещённое значение 0 всегда принадлежит этому отрезку, получаем, что число треугольников с вершиной (a,b) равно t1-t0. 
Перебираем все точки (a,b), считаем t1-t0 и суммируем.
Всё. Сложность N^2*log(N), основное время тратится на вычисление НОД.
Если надо быстрее - надо будет думать. Скорее всего, надо будет перебирать взаимно простые пары (a1,b1), считать, сколько точек попало в перекошенный квадрат (переведённый в базис (a1,b1), (-b1,a1)), искать для них формулу и суммировать. Может быть, получится, может быть, нет. Какого порядка N?
Есть вот какие мысли по оптимизации:
1) проверять прямой угол в точке с помощью скалярного произведения. 
(Ax*Bx+Ay*By)/|a|+|b| = 1 
2) проверять не на соответствие прямоугольника а только угол в первой точке.
3) проверять на прямой угол только вершины находящиеся под прямой x=y, и результат умножить на 2. Только нужно осторожно обработать случаи когда прямой угол лежит на ней.
4) В качестве второй точки перебирать не все точки а только те которые находятся внутри квадрата описанного вокруг окружности с центром в между (0,0) и нашей точкой, и снаружи вписанного в ту же окружность.
5) Можно просто по этой окружности идти: увеличиваем x, проверяем целый ли y. Нам даже не придется проверять угол на прямой. 
Питона я не знаю, по этому не вижу где в примере делится на 2. Иначе каждый треугольник становится посчитан два раза.