GCD 2 (spoj) , num b is type string

GCD2

in spoj though seems to e bit of tedious and boring question , its really small and has some good coding concept behind it which can be used when we encounter a situation where need a a big string to be handled and at the same time we need to find the gcd of it.

solu

we can take the bigger num input as a string and while converting it number be do %a all the time , and apply the normal procedure. :P

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<string.h>
5. int gcd(int a,int b){
6. if(b==0)
7. return a;
8. else
9. gcd(b,a%b);
10. }
12. int main(){
13. int t;
14. scanf("%d",&t);
15. while(t--){
16. int a,i,len,b=0;
17. char n[250];
18. scanf("%d%s",&a,n);
19. len=strlen(n);
20. if(a==0){
21. printf("%s\n",n);
22. continue;
23. }
24. for(i=0;i<len;i++)
25. b=(b*10+(n[i]-'0'))%a;
26. printf("%d\n",gcd(a,b));
27. }
28. return 0;
29. }