| Submit | All submissions | Best solutions | Back to list |
FNRANK - Rank of a Fraction |
Let us consider a set of fractions x/y, such that 0 <= x/y <= 1, y <= n and gcd(x, y) = 1.
For example, say n = 5. Then we have the following set in increasing order :
You are given n, a and b. The task is to find the rank of a/b in a set of fractions as stated above which is in increasing order.
Input
The first line of the input contains t (t <= 20), the number of test cases. Then t lines follow. In each of the t lines you are given n, a and b. (n <= 100000).
Output
Print t lines. The ith line contains the rank of a fraction a/b for a given n, a and b in the (i + 1)th line of input. All answers fit within a signed integer.
Example
Input: 2 5 3 4 8 5 7 Output: 9 17
| Added by: | Paranoid Android |
| Date: | 2010-03-07 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | Based on the problem FRACTION |
hide comments
|
2022-02-23 22:14:55 David
First Java solution! |
|
|
2020-08-03 20:58:53
Use of inclusion and exclusion property!! |
|
|
2020-06-15 13:58:27
use long long costed 10WA |
|
|
2019-09-02 04:40:32 Farhan Hasin
Let's get to all X from 1 to N and check how many Y/X are there who are less than A/B and gcd(X, Y)=1. To do this, first of all, Y/X < A/B, so Y<(A*X)/B. So all we have to do is to find the count of Y so that Y<(A*X)/B and gcd(X, Y)=1 for all X. We can do that with the Mobius function. Last edit: 2019-09-02 04:41:40 |
|
|
2015-01-31 18:38:04 parijat bhatt
am using the the formula to generate its next numbers but still tle:( |
RSS