Monday, 15 December 2014

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>
  4. int gcd(int a,int b){
  5. if(b==0)
  6. return a;
  7. else
  8. gcd(b,a%b);
  9. }
  10. int main(){
  11. int t;
  12. scanf("%d",&t);
  13. while(t--){
  14. int a,i,len,b=0;
  15. char n[250];
  16. scanf("%d%s",&a,n);
  17. len=strlen(n);
  18. if(a==0){
  19. printf("%s\n",n);
  20. continue;
  21. }
  22. for(i=0;i<len;i++)
  23. b=(b*10+(n[i]-'0'))%a;
  24. printf("%d\n",gcd(a,b));
  25. }
  26. return 0;
  27. }