VLATTICE - Visible Lattice Points
Consider a N * N * N lattice. One corner is at (0, 0, 0) and the opposite one is at (N, N, N). How many lattice points are visible from corner at (0, 0, 0)? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.
Input
The first line contains the number of test cases T. The next T lines contain an integer N.
Output
Output T lines, one corresponding to each test case.
Sample
Input: 3 1 2 5 Sample Output: 7 19 175
Constraints
T <= 501 <= N <= 1000000
hide comments
|
trijeet:
2017-10-24 09:01:56
Recursion works, just precalculate up to 10^3. cheers (y) |
|
jiaxinwei:
2017-08-04 10:11:02
nice! for following god-cow kuangbin |
|
kuangbin:
2013-08-21 10:55:42
Nice! |
|
Lu Qi:
2013-04-22 11:51:30
nice problem!!! Last edit: 2013-04-22 13:58:27 |
|
Pradeep Verma:
2011-06-21 02:59:27
suggest one two more test cases..... |
|
Chetan Gupta:
2011-06-13 17:30:51
i am getting tle.. it is taking 2.67 sec on ideone for the worst case i.e T=50 and N=1000000 for all test case.
|
| Added by: | Varun Jalan |
| Date: | 2010-07-29 |
| Time limit: | 1.368s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 VB.NET |
| Resource: | own problem used for Indian ICPC training camp |
RSS