VLATTICE - Visible Lattice Points

no tags 

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 interger N
 
Output :
Output T lines, one corresponding to each test case.
 
Sample Input :
3
1
2
5
 
Sample Output :
7
19
175
 
Constraints :
T <= 50
1 <= 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.....

Gurpreet Singh: 2012-03-27 23:56:31

Last edit: 2011-06-18 19:36:42
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.

EDIT: Finally Accepted

Last edit: 2011-06-14 08:01:57

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