The Silence of the Lamps
Time limit1sMemory limit512 MB
Count triples of integer side lengths (all distinct pairs give different areas) with volume at most N, so no face is a square and the three sides are pairwise distinct.
- Level
Medium6 of 10
- Topics
- Math, Number theory, Brute force, Implementation
- Solved
- No attempts yet
Problem
First, for those who have never seen a lamp before, let's say it is a cuboid (box with rectangular faces) made of glass and filled with gas. All sides of a lamp have integer lengths.
Once upon a time, our lecturer was sentenced for destroying lamps on a street. He must have gone somewhat crazy, as he thought some of the lamps were screaming at him in high-pitched voices.
In his beautiful mind, he followed a weird pattern. He only recognized and destroyed those lamps which had no square face and whose volume did not exceed a fixed value. Later, during a session with his doctor Clarice, he said he was very scared of large objects and of objects with too regular shapes.
Your task is to count all possible shapes matching lecturer's conditions.
Input
The first input line contains a number T of test cases (1 ≤ T ≤ 105). Each of the next T lines contains a single integer N (1 ≤ N ≤ 106), the maximum recognizable volume of a lamp.
Output
For each test case output the number of different lamp shapes which could have been destroyed in the rage.