gcd2:easy(logic not clear)

general
,
1

hey guys.i was trying to understand the logic behind this problem but just could not figure out anything from accepted solution.I dont understand why do they take mod a at every step…

int mod(int a, char b[])
{
    int r = 0;
    int i;
    for(i=0;b[i];++i)
    {
      r=10*r +(b[i] - 48);
      r = r % a;//basically i dont understand this line......    <--------
    }
return r;
}

and secondly i dont understand how to deal with the question in which one number is of some 250 or digits like that

2

The main point here is

gcd(b,a)= gcd(a,b%a);

Thus, here we have the big integer B(250 digits), we calculate gcd as RHS says i.e. B%a. Now, we don’t have any datatype which can accept number of 250 digits and hence, we take the number as a string. Lets say we have a three digit number ABC. The number can be expressed as:

ABC= 100*A+ 10*B + C;
(ABC)%MOD= (100*A+ 10*B +C)%MOD;
         = ((100*A)%MOD + (10*B)%MOD + C%MOD)%MOD;  // By the property of modulo operator
         = (((100%MOD)*(A%MOD))%MOD + ((10%MOD)*(B%MOD))%MOD + C%MOD)%MOD;
       or
     (ABC)%MOD=  (A*100)%MOD + (BC)%MOD; // this cab be expanded further in the above manner.
So, you can see here, ABC%MOD is basically modulus of the numbers which appear in the expression when we express it in the powers of 10.

So, we are as per this code calculating this way:
lets say string is 12= 10+ 2. Number in powers of 10 is the value of r in every iteration.

for(int i=0;i<len;i++)
{
   r= 10*r +(b[i]-'0');  
   // initially r=0, number is r= 0+ (1); r=1 =(1)%4=1;` // then in next iteration, r is 1, number is 
   //r= 1*10 + (2)=12(see here the value of r here is the actual value represented by the string) r=12.
   r=r%a;
}
3 Likes
3

thanks a lot…that was well explained :slight_smile:

1 Like
4

Btw what is the category of these type of question(in which we have to take as string and then manipulate).//just asking so that i can master on this type of question(quite weak on this). :slight_smile:

1 Like
5

As such we cannot classify them, but usually we do such when the input is very large. Also, lets say you have a question in which you have to deal with the digits of the input, then you may take it as a string instead of taking int integer input and then evaluating the digit by % operator and a while loop. There may be many, but i remember these right now: http://www.codechef.com/JUNE14/problems/FORGETPW/
http://www.codechef.com/SEPT14/problems/FACTORIZ/
http://www.codechef.com/APRIL14/problems/ADIGIT/
and many others I may have done, I’ll update the list if i’ll get more.

6

@damn_me your lines "lets say you have a question in which you have to deal with the digits of the input, then you may take it as a string instead of taking int integer input and then evaluating the digit by operator and a while loop"--see above comment...evaluating the digit by operator and a while loop…is this called hashing??

7

No… that’s not the category in which you can put in. Hashing is something more towards a key that maps to a value. Now, we can code multiple keys to map a certain value r vice versa. EX: an array, this is also a form of hashing in which every index hashes to a particular array value.

1 Like