Chef and Weird Queries
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
When the final results for the employement competition were announced, Nour Eddin Ramadan was thrilled to find his name among the accepted co-Chefs.
However, after a while Nour started wasting time at the kitchen. He would usually spend hours talking to girls, and he even invited a girl to the kitchen pretending that he is the most valuable employer at Chef's restaurant.
When Chef found out about it, he decided that it was time to teach Nour a lesson. Before going home that night, Chef called Nour to his office and asked him to solve the following problem, saying that he better come to work tomorrow with a solution for it, or otherwise, it would be better if he doesn't come at all:
Given T queries, where each query contains a single number Y, Nour has to find the number of pairs A and B, such that the following equation holds true:
A2 + B ≤ Y
Where A is any positive integer, and B holds (1 ≤ B ≤ 700).
Nour was really busy that night (Yeah he got that girl to go out with him after all!), and he asked for your help.
The first line contains T denoting the number of test cases.
T lines follows, Each line contains a single integer Y denoting the right side of the formula.
For each test print a single line, containing a single number, indicating the answer for the test.
- 1 ≤ T ≤ 105
- 1 ≤ Y ≤ 1010
- Note that A must be any positive integer, and B must hold 1 ≤ B ≤ 700.
Input: 4 2 3 4 10000000000 Output: 1 2 3 69999300
|Tags||cook87, mhammad1, saeed_sryhini, simple, sorting, two-pointers|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.