- Practice
- Functional Programming
- Ad Hoc
- Huge GCD
- Discussions

# Huge GCD

# Huge GCD

jarmex + 0 comments it is really easy to use the bigint structure (F#)

ismailmarmoush + 1 comment What does this part mean

`But instead of printing complete answer you have to print answer modulo 109+7.`

Also the explaination of test case 2 is not related to how actually the method should be solved, there would be no way of discovering such pattern of 2^a and 3^a

abhiranjan + 2 comments Hi, as the output can be very large (exceeding the limits of 64 bits integer) modulo operation common way to check the correctness of output.

It is only a explanation that first series is power of two, while second is power of three. You don't have to find such patter.

dolgov_vv + 2 comments The task is not about Functional Programming. It's a pure Number theory.

abhiranjan + 1 comment Yep, that's why it's placed in MISC chapter :)

Jonnymoo + 0 comments You wouldn't happen to have a handy link the number theory side of it would you?

carl_smotricz + 0 comments It's possible to fiddle with lists of factors to keep numbers small, and that would be Number Theory.

But it's also possible to do what I did and use some implementation of Big Integers to actually simply multiply those numbers out, find their GCD, modulo it to 1000000007 and print it out.

julius_angres + 0 comments One-liner in Haskell (no focus on performance though):

`solve :: [Integer] -> [Integer] -> Integer solve ns ms = flip mod (10^9 + 7) $ gcd (product ns) (product ms)`

weozUA + 0 comments Scala solution:

import scala.io.StdIn object Solution extends App { def gcd(x: BigInt, y: BigInt): BigInt = { if (x == 0) y else gcd(y % x, x) } def product(nums: String): BigInt = { nums.split(" ").map(BigInt(_)).product } val f = () => StdIn.readLine() val (_, a, _, b) = (f(), product(f()), f(), product(f())) println(gcd(a, b) % 1000000007) }

Sort 11 Discussions, By:

Please Login in order to post a comment