Need help in codeforces problem!

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.

@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( )

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

I think this will help you understand the solution, it is very well written.

thanku @vbt_95

thanku …now i got it …