I am not getting the logic behind using gcd to find finite division condition in the editorial of given problem, guys please help me understanding editorial of this problem in codeforces.
http://codeforces.com/contest/983/problem/A
@vijju123 @vivek_1998299 @abdullah768
I hope you know how to convert fractional part of decimal base number into binary base.
Try to extend it by dividing a smaller number with a larger one in some other base b . You will find that at each step of division we will be doing r=(rb)%q . After some point of time if r=0 then we are done .In simple words if (pb^k)%q=0 for some k then fraction will be finite .
Someone there posted this explanation too( https://s1.ax2x.com/2018/05/16/xuSrY.jpg )
As you asked the logic behind using gcd, here is my explanation- In this question, we want to find whether q divides b^k or not. _It is possible only when all prime factors of b are prime factors of q also.
Here is a pseudocode b = gcd(q, b);
while (b != 1) // /*means q and p are not relatively prime*/
{
while (q % b == 0) q /= b;
b = gcd(q, b);
}_
After all iteration if (q == 1) then k exists otherwise not.
Here is an example-
let b = 12 and q = 8
prime factors of b = 2 * 2 * 3 and q = 2 * 2 *2. We will find whether all prime factors of q are prime factors of k using gcd.
GCD of b and q is 4 (common prime factors of b and q) We will divide q by gcd until (q % gcd != 0) (This will remove all factors of q which makes gcd).
New value of b = gcd and q = 2. We repeat the same process until b and q becomes coprime. If q == 1 means all factors of q are present in b hence k exists, otherwise not.
Another example-
b = 8 and q = 12
GCD will be same but at the end of the loop q = 3, which is not a factor of 8 hence k doesn’t exist.
Thus we used GCD to show all factors of q are present in b or not
Hope it helps, feel free to ask any doubt
thanku …now i got it …
