Queer Triplets
Problem:
practice
Tags: Number Theory
Author: Kaustav.
Tester: Shami.
This problem is a trick question. If you were to solve it with brute force taking the question too seriously you will time out. Here is the solution
Yes, the bounds of 10^18 (later reduced to 10^16) will not let you converge in time for the solution. You have to figure out the actual bound of I,j and k to compute them in time. Even if you were to pick lesser constraining bound say 100 you would have got the solution. The bounds you compute are 2 <= i,j,k <= 11. The way you go about is that if you are to notice ii-k, kj-I and j*i-k are symmetric where every permutation of the i,j, and k has to satisfy the constraint. Hence if you are to only consider the i<=j<=k go and plug i=0,1,2,… you will soon discover that the bound on i is 2<=i<=3. You then move the analysis to discover bounds of j to be actually bounded by only 2 and 5 and k to be only 2 and 11. Given this bound just run to see the satisfiability of the the constraints and you will have the all of the solution.