Problem Statement
The greatest common divisor of two positive integers p and q, denoted gcd(p,q), is the largest d such that d divides p and d divides q. Two positive integers p and q are called coprime if their greatest common divisor is 1. For example, 15 and 44 are coprime but 21 and 35 are not (because gcd(21,35) = 7).
You are given N queries. The parameters for these queries are given in the long[] X and in the int[] Y. These contain N elements each.
For each valid i, answer the following query: Let x = X[i] and y = Y[i]. Consider the closed interval [x, x+y-1]. How many numbers in this interval are coprime with y?
Return a int[] with N elements: for each valid i, the answer to the query given by X[i] and Y[i].
Definition
- Class:
- OneGcd
- Method:
- solve
- Parameters:
- long[], int[]
- Returns:
- int[]
- Method signature:
- int[] solve(long[] X, int[] Y)
- (be sure your method is public)
Notes
- The values in Y are guaranteed to have a special form, as described by the last constraint. (Note that the problem can also be solved without this constraint.)
Constraints
- N will be between 1 and 500, inclusive.
- X will have exactly N elements.
- Y will have exactly N elements.
- All numbers in X and Y will be positive.
- For each valid i, Y[i] will be at most 10^7.
- For each valid i, X[i] + Y[i] will be at most 10^18.
- For each valid i, Y[i] will not be divisible by any prime greater than 10. (I.e., each Y[i] will have the form 2^a * 3^b * 5^c * 7^d, for some a, b, c, d >= 0.)
Examples
{5 , 3}{3 , 7}Returns: {2, 6 }In the interval [5 , 7] : 5 and 7 are coprime with 3 In the interval [3 , 9] : 3 , 4 , 5 , 6 , 8 , 9 are coprime with 7{10}{15}Returns: {8 }In the interval [10 , 24] : 11 , 13 , 14 , 16 , 17 , 19 , 22 , 23 are coprime with 15.
Back to all problems