O(1) approach to solve Codeforces Round 368 (Div. 2) Problem C

Правка en1, от hetanhnandre, 2023-05-15 21:33:30

Problem — 707C - Pythagorean Triples

Let's consider a triangle with sides n, m, and k.

According to the Pythagorean Theorem, we know that n² + m² = k².

By rearranging the equation, we have k² — m² = n².

Further simplifying, we find that (k + m)(k — m) = n².

n² can be represented as n²*1.

Therefore, we can assume that k + m = n² and k — m = 1

By adding and subtracting these equations, we obtain k = (n² + 1)/2 and m = (n² — 1)/2.

This solution is valid when n is an odd number since we assume k — m = 1.

So, how to handle the case when n is even?

To handle even values, we can observe the following pattern: If (k — m) is odd, the solution is applicable to odd values of n. Conversely, if (k — m) is even, the solution is applicable to even values of n.

Set k = (n^2 + 2n) / 4 Set m = (n^2 — 2n) / 4

From this we get, k = (n*n-1)/4 and m = (n*n)/4)+1

Link to My Solution : 206019093

Теги math, geometry, div2c

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский hetanhnandre 2023-05-15 21:33:30 1052 Initial revision (published)