# Problem Link

# Difficulty

Easy

# Pre-requisites

Basic math

# Problem

Given an equilateral triangle having length of each side as an integer **N**. Is it possible to alter one of its’ sides such that the height drawn to the altered side has integral length and the altered side has an even integer length?

# Explanation

Let’s recall the formula for calculating of length of the height of an isosceles triangle. If the length of the height is **h**, the length of the altered side is **b**, then **h = sqrt(N ^{2}-b^{2}/4)**. Then,

**h**. Let’s denote

^{2}=N^{2}-b^{2}/4**b/2**by

**c**and, since

**b**should be even,

**c**should be integer. Then, we get

**h**. This is the same as

^{2}=N^{2}-c^{2}**N**. According to the statement,

^{2}=h^{2}+c^{2}**h**and

**c**should be integer.

Now, the problem is: given an integer **N**. Find out, whether it is possible to represent **N ^{2}** as a sum of two integer numbers’ squares or not.

### How to get 10 points

Let’s iterate through possible values of **h**, there are **O(N)** possible values of **h**. Then, let’s check, if **N ^{2}-h^{2}** is a square of an integer number.

The total complexity of such a solution is **O(TN)** and it is capable only of solving the first subtask.

### How to get 100 points

It is a well known fact that **N** can be represented as a sum of two perfect squares if and only if **N** is dividible by a prime of the form **(4k+1)**, where **k** is an integer number.

So, let’s find all the prime numbers not exceeding the maximal value of **N**. Then, let’s pick all the prime numbers that give **1** modulo **4** and for each of them, mark all the numbers that are divisible by them and doesn’t exceed the maximal possible value of **N** (say, **MAX_N**).

It takes **MAX_N/P** operations to mark all the integers that are divisible by **P**. Let’s estimate the total number of the operations that we will make.

Since not every number is a prime of the form **(4k+1)**, we can safely assume that the total number of operations won’t exceed \sum_{P=1}^N \frac{N}{P} that won’t exceed **O(T+MAX_N log MAX_N)**.

This solution gets 100 points.

# Setter’s Solution

Can be found here

# Tester’s Solution

Can be found here