I have a number A and a number B(which is very large calculated by NcR or C(N,R) modulo 10e9+7) and i want to find A^B(A raise to the power B) but by fast exponentation i get wrong answer. Like for example A=2 and B=6 and mod=5 then actual answer is(2^6)%5=4 but since i have to use mod at every step my answer is (2^(6%5))%5=2. I can't store B in a number because it's too large.How should i go about it?Thanks in advance.
This is a problem from an ongoing contest.
Did i ask a solution to the problem or just a small part (that too computational) of it? Moreover these contest are to learn a new thing and so i wanted to learn this thing.You also know this is just the last part of the problem and to reach here you've to use your brain and from here it's just some technique which someone knows and some don't.Therefore i want to know the technique.If you don't want to help then it's Okay.Maybe you find it asking the solution.I searched google for the answer but couldn't get it therefore i asked it here.You mean i should sit idle without looking to learn this technique.I know i'll learn faster if i get to know this now.Please brother don't think otherwise for me.
guess you didn't google hard enough
How big can B be?
C(5000,2500)
It can be computed using ((A%mod)^(B%(mod-1)))%mod
hey don't give spoilers for ongoing contests..
I just want to know that did you invent this technique?You also got to know from somewhere only so what's the point when i am just learning a technique and NOT AT ALL asking for solution.
I don't know which contest specifically where you need this technique for a problem, but in general, contests are meant for competition so it's not fair that you get outside help while the other contestants don't. If you wanted to learn, you could do problems from online judges where it (probably) wouldn't be against any rules to help on them.
After calculating B normally ? I mean by using mod at every step to calculate B?