You are not logged in. Please login at www.codechef.com to post your questions!

×

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. http://codeforces.com/contest/983/problem/A @vijju123 @vivek_1998299 @abdullah768

asked 19 May '18, 20:55

deep143's gravatar image

2★deep143
12
accept rate: 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

link

answered 19 May '18, 23:06

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

thanku ...now i got it ...

(19 May '18, 23:13) deep1432★

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 )

link

answered 19 May '18, 21:17

vbt_95's gravatar image

4★vbt_95
4406
accept rate: 27%

thanku @vbt_95

(19 May '18, 21:27) deep1432★

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

link

answered 19 May '18, 23:41

siddharthp538's gravatar image

4★siddharthp538
2555
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×631
×1

question asked: 19 May '18, 20:55

question was seen: 221 times

last updated: 19 May '18, 23:41