RATIONAL - Rational Number
Given a number N, find the number of positive irreducible rational numbers less than 1 such that when expressed as P/Q, both P, Q are less than or equal to N.
Input
The first line contain a single integer T, the number of test cases. Following T (<= 1000) lines will contain a test case, a single number N (<= 1000000).
Output
For each test case print the output on a single line.
Example
Input:
3
1
2
3
Output: 0
1
3
hide comments
Anil Kishore:
2009-11-28 13:12:14
given N, we have to find number of irreducible rational numbers of the form P/Q ( < 1 ) and P,Q<=N. For N = 3 (ans=3)--> 1/2 , 1/3 , 2/3. For N = 4 (ans=5)--> 1/2 , 1/3 , 2/3 , 1/4 , 3/4 |
|
D3V D PR():
2009-11-25 14:39:26
explain the question a bit more (with a example ) |
Added by: | Hemant Verma |
Date: | 2009-11-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | Codechef Snackdown 2009 |