Binary Search? When Jojo was a little kid, his teacher asked him a question. What was the answer of 1^2+2^2+3^2+...+N^2? Of course that problem was hard enough for a primary student. Buts ince he is a university student, and he knows that the answer is 1/6∗N∗(N +1)∗(2N +1), such problem is to easy for him. Now Jojo came up with a new problem. If he has an integer M, what is the smallest integer N such that 1^2 + 2^2 + 3^2+ ...+N^2 is greater than or equal to M. After thinking for some time, he came up with a solution, but his solution takes a lot of time. Since you are his nemesis, he challenges you to solve the problem quicker than him. Of course you accept his challenge! Format Input The first line is an integer T representing the number of test cases. For each test case there will be 1 line consisting of an integer M. Format Output For each test case output “Case #X: N”. X is the test case number and N is the smallest integer such that 1^2 + 2^2 + 3^2+ ...+N^2 is greater than or equal to M. Constraints • 1 ≤ T ≤ 2000 • 1 ≤ M ≤ 1018 Sample Input 1 (standard input) 1 2 Sample Output 1 (standard output) Case #1: 2 Sample Input 2 (standard input) 1 10 Sample Output 2 (standard output) Case #1: 3 Use C language.
Binary Search?
When Jojo was a little kid, his teacher asked him a question. What was the answer of 1^2+2^2+3^2+...+N^2? Of course that problem was hard enough for a primary student. Buts ince he is a university student, and he knows that the answer is 1/6∗N∗(N +1)∗(2N +1), such problem is to easy for him. Now Jojo came up with a new problem. If he has an integer
M, what is the smallest integer N such that 1^2 + 2^2 + 3^2+ ...+N^2 is greater than or equal to M. After thinking for some time, he came up with a solution, but his solution takes a lot of time. Since you are his nemesis, he challenges you to solve the problem quicker than him. Of course you accept his challenge!
Format Input
The first line is an integer T representing the number of test cases.
For each test case there will be 1 line consisting of an integer
M.
Format Output
For each test case output “Case #X: N”. X is the test case number and
N is the smallest integer such that 1^2 + 2^2 + 3^2+ ...+N^2
is greater than or equal to M.
Constraints
• 1 ≤ T ≤ 2000 • 1 ≤ M ≤ 1018
Sample Input 1 (standard input)
1
2
Sample Output 1 (standard output)
Case #1: 2
Sample Input 2 (standard input)
1
10
Sample Output 2 (standard output)
Case #1: 3
Use C language.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
