Harbin's blog

By Harbin, history, 11 months ago, In English,

In this problem ([192A Funky Numbers](https://codeforces.com/contest/192/problem/A)), given an integer 'n', find if it can be the sum of two triangular numbers where a triangular number equals k(k+1)/2 for some positive integer k.

I have two questions regarding this problem.

  1. In many solutions I saw, people would increment and int i from i to Math.sqrt(n) and use this value to find the k value for the second triangular number by using the equation n — (i(i+1)/2). Why stop at Math.sqrt(n)?

  2. Following the above algorithm, k2 (the k of the second triangular number) could be found as such:

int k2 = (int)(Math.sqrt((n — (i*(i+1)/2)) * 2));

This time, why is Math.sqrt() used, and why is the result multiplied by 2?

Thank you for your help, Codeforces community.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

1- n<=1e9 so if you go over sqrt(n) (which is nearly 3e4) ,consider i=1e5 which is greater than the sqrt then the (i)th triangular number will be((i*(i+1))/2)=1e10 which is greater than n, so you only need to iterate to sqrt n.

2-you want to check if there is sum of two triangular numbers is equal to n, so consider we have k1,k2. (k1*(k1+1))/2 + (k2*(k2+1))/2 = n . we get k1 by iterate for all numbers <= sqrt(n) ((brute force)) and for each k1 we have : (k2*(k2+1))/2 = ( n — (k1*(k1+1))/2 ) now you can easily see that : k2*(k2+1) = ( n — (k1*(k1+1))/2 ) * 2 (this is why we multiply by 2. then also you can see that : k2 < sqrt( ( n — (k1*(k1+1))/2 ) * 2 ) < (k2+1) while [sqrt( ( n — (k1*(k1+1))/2 ) * 2 )] is a real number not an integer, so : (int) ( sqrt( ( n — (k1*(k1+1))/2 ) * 2 )) will give you k2. now you just need to check if : (k1*(k1+1))/2 + (k2*(k2+1))/2 = n then print yes if not continue with k1+1 and so on till sqrt(n)

hope this help you :)