Returns (x numerator / denominator), which is assumed to come out to an integral value.
(long x, long numerator, long denominator)
| 941 | |
| 942 | |
| 943 | static long multiplyFraction(long x, long numerator, long denominator) { |
| 944 | if (x == 1) { |
| 945 | return numerator / denominator; |
| 946 | } |
| 947 | |
| 948 | long commonDivisor = gcd(x, denominator); |
| 949 | x /= commonDivisor; |
| 950 | denominator /= commonDivisor; |
| 951 | // We know gcd(x, denominator) = 1, and x * numerator / denominator is exact, |
| 952 | // so denominator must be a divisor of numerator. |
| 953 | return x * (numerator / denominator); |
| 954 | } |
| 955 | |
| 956 | /* |
| 957 | * binomial(biggestBinomials[k], k) fits in a long, but not binomial(biggestBinomials[k] + 1, k). |