I got the concept but had a little doubt that when p goes above and we take (b % (p-1)). Now p-1 is 10^9+6. Then we divide p-1 into 2 factor:- 2 * (5* 10^9 + 3). We solve b%(5*10^9 + 3) seperately . But what about b%2?
POWPOW2(hard) doubt
we first divided our situation into two cases , b is odd or b is even , so for odd number b%2=1 and for even b%2=0
ok. It was (b^(2nCn)) % (2*(510^8+3))
If b is odd then b%2=1 (I got this)
but 2 and 510^8+3 are in multiplication.
Are you saying that b% (2 * (510^8+3)) = (b%2)(b%(5*10^8+3)) ?
If no, then can you please explain a little more? Thanks in advance.
yes you are right you can see the video around 12:00 to understand this rule
I still didn’t understand why b%2 is not considered
I still didn’t understand where is b%2. Can you please explain ? Thanks in advance.
okay try this
https://www.quora.com/How-do-I-solve-Power-with-Combinatorics-HARD-on-SPOJ
this has elaborate explanation
Thanks…I got it
please mark your doubt as resolved
When b is odd (b^(2nCn)) % (2*(5 10^8+3)) becomes (b^( (2nCn) % (510^8+2)) % (mod)
Is mod 510^8+3 or 10^9 +6?
Sir wrote mod = (510^8+3) but after reading the blog i think it should be 10^9+6. Can you help?
(5 *10 ^8 +3)*2== 10^9 +6
so sir wrote correct