someone please help me understand the GCD2 problem in the practice (easy) section of codechef and please explain the solution ,i am not able to solve this problem …please help .
Scan the variable B as a string find mod of the numeric string with A
sum = 0
Loop(I,B.length()){
sum = (sum*10 + B[i]-‘a’)%A
}
Print(GCD(A,SUM))
See this
can you please explain the purpose of line sum=(sum+B[i]-‘a’)%A .
In the question , as you can see B is a very large integer , so you have to input it as a string . Now in
that line he is just changing string to integer , you can also write it as sum = (sum*10) + B[i] - ‘0’;
Now you are thinking why (%A). Because whenever B becomes larger than A it will decrease it and make it smaller than itself. NOW you must be thinking , Why it will not affect the result , because in GCD we take the mod of the greater number/ smaller number.So, the answer won’t get affected.
nicely explained the solution …i understood the solution .keep doing this good work.
@riddle279 to better understand this type of question (like Modular arithmetic) –
see my articles on geeksforgeeks