ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1335. White Thesis

(n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by manishmmulani 6 Jan 2008 02:34
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by Rustambek_UWED 7 May 2008 17:44
Thank you very much for the formula. I can prove it. But had not found it.
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by Desperados[KhAI] >> Starov_Lesha 15 Jun 2008 15:58
Something very dark...
The solution is more easy and more easy to understand too!
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by Denis Koshman 24 Jul 2008 16:09
n^2+n, n^2+2n, n^2
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by Megatron 10 Mar 2009 10:49
I can prove it . but i don't know how did you come out with that?
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by IgorKoval(from Pskov) 3 Dec 2011 03:37
Megatron wrote 10 March 2009 10:49
I can prove it . but i don't know how did you come out with that?

It's simple.
Just c=n^2 ( by intuition ). So, find a and b.
a=n^2+c and b=n^2+d ( because n^2 <= a,b,c <= (n+1)^2 = n^2 + 2*n + 1 ), where c and d is positive and c!=d( because a!=b(by text of this problem ) )

a^2 + b^2 = (n^2+c)^2 + (n^2+d)^2 = 2*n^4 + 2*n^2(c+d) + c^2 + d^2

Look at this 2*n^4 + 2*n^2(c+d) + c^2 + d^2. Each summand must be divisible on c=n^2.
So, just, c = n and d = 2*n
Answer:
a = n^2 + n
b = n^2 + 2*n
c = n^2

P.S.:
You can say just a = n^2 and analogous prove another formula.

Edited by author 03.12.2011 03:41
Re: (n*n) (n*n + n + 1) (n*n + 1) =====> O(1) soln
Posted by LyanA 21 Jan 2013 20:11
i was very surprised
it's just 3 strings of code
you're perfect =)