GCD2 Problem : EASY

In solutions of participants most of them have divided each digit of the very large number(10^250) with the other number for finding HCF ?

Any1 knows why is it so ? which algorithm is it ?

3 Likes

If the very large number is represented by 3 digits (ABC), the actual number is ((A x 10) + B) x 10 + C.

Note that
(a x b) mod m = ((a mod m) x b) mod m and
(a + b) mod m = ((a mod m) + b) mod m

Maybe this helps you understand how the other solutions work.

6 Likes

@renze thanks a lot