Returns (x numerator / denominator), which is assumed to come out to an integral value.
(long x, long numerator, long denominator)
| 958 | |
| 959 | |
| 960 | static long multiplyFraction(long x, long numerator, long denominator) { |
| 961 | if (x == 1) { |
| 962 | return numerator / denominator; |
| 963 | } |
| 964 | |
| 965 | long commonDivisor = gcd(x, denominator); |
| 966 | x /= commonDivisor; |
| 967 | denominator /= commonDivisor; |
| 968 | // We know gcd(x, denominator) = 1, and x * numerator / denominator is exact, |
| 969 | // so denominator must be a divisor of numerator. |
| 970 | return x * (numerator / denominator); |
| 971 | } |
| 972 | |
| 973 | /* |
| 974 | * binomial(biggestBinomials[k], k) fits in a long, but not binomial(biggestBinomials[k] + 1, k). |