GCD2 ALGORITHM

general
, , ,
1

Can anyone pls explain the algorithm for gcd2 problem.?..i am stuck here…i referd many solutions but i am not undertanding what they r doing…

2

The following solution is clear :

#include<stdio.h>
char b[300];
int rem(int a) {
        int p=0,i;
        for(i=0;b[i]!= '\0';i++) p = ((b[i]-'0')+p*10) %a;
        return p;
}

int gcd(int a,int b) {
        if(b==0) return a;
        else gcd(b,a%b);
}

int main() {
        int i,j,a;
        scanf("%d",&i);
        while(i--) {
                scanf("%d %s",&a,b);
                if(a == 0) printf("%s\n",b);
                else {
                        int p = rem(a);
                        printf("%d\n",gcd(a,p));
                }
        }
        return 0;
}

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.

credits to @renze

gcd(B,A)=gcd(A,B%A) if B is in BIGINT and A is in INTEGER (B%A) will be an integer.

3 Likes