×

# Need help in codeforces problem!

 0 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 asked 19 May '18, 20:55 2★deep143 1●2 accept rate: 0%

 0 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 answered 19 May '18, 23:06 4★pant0000 111●4 accept rate: 10% thanku ...now i got it ... (19 May '18, 23:13) deep1432★
 0 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 ) answered 19 May '18, 21:17 4★vbt_95 440●6 accept rate: 27% thanku @vbt_95 (19 May '18, 21:27) deep1432★
 0 I think this will help you understand the solution, it is very well written. answered 19 May '18, 23:41 255●5 accept rate: 11%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

question asked: 19 May '18, 20:55

question was seen: 221 times

last updated: 19 May '18, 23:41