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

# Need help in codeforces problem!

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=(r*b)%q . After some point of time if r=0 then we are done .In simple words if (p*b^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 …