| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
2009-11-28 13:12:14 Anil Kishore
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 |
|
|
2009-11-25 14:39:26 D3V D PR()
explain the question a bit more (with a example ) |
RSS