Please subscribe to the official Codeforces channel in Telegram via the link ×

A simple way to solve Round368 Div.2 Problem C

Revision en1, by PengsenMao, 2016-08-21 11:49:44

First, suppose n is the shortest side of the triangle, m, k are other two sides. According to Pythagorean Theorem, we know (n^{2}+m^{2}=k^{2})

just do a change (k^2-m^2=n^{2})

futherly ((k+m)(k-m)=n^{2})

as we know, (n^{2}\times1=n^{2}) so we can suppose that (k+m=n^{2},k-m=1) [because we have SPJ]

easily, we get (k=\frac{n^{2}+1}{2},m=\frac{n^{2}-1}{2})

because the side is a interger, so this solution can only be used when n is a odd.

So how to deal with even? we find that if (k-m) is odd, the solution is suitable for odd. On the other hand, we guess that if(k-m) is even, the solution is suitable for even.

just as this, (k+m=\frac{1}{2}n^{2},k-m=2)

so, we get (k=\frac{1}{4}n^{2}+1,m=k-2)

this is an (O(1)) algorithm.

[my english is not very good, so please pass some grammer fault.:P]

Tags math


  Rev. Lang. By When Δ Comment
en3 English PengsenMao 2016-08-21 12:09:23 230
en2 English PengsenMao 2016-08-21 11:54:22 312
en1 English PengsenMao 2016-08-21 11:49:44 893 Initial revision (published)