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…

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.

5 Likes