### small_doubt's blog

By small_doubt, history, 6 years ago,

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.

• -26

| Write comment?
 » 6 years ago, # |   +7 This is a problem from an ongoing contest.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -52 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.
•  » » » 6 years ago, # ^ |   0 guess you didn't google hard enough
 » 6 years ago, # |   -13 How big can B be?
•  » » 6 years ago, # ^ |   -13 C(5000,2500)
 » 6 years ago, # |   -22 It can be computed using ((A%mod)^(B%(mod-1)))%mod
•  » » 6 years ago, # ^ |   +9 hey don't give spoilers for ongoing contests..
•  » » » 6 years ago, # ^ |   -28 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.
•  » » » » 6 years ago, # ^ |   +17 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.
•  » » 6 years ago, # ^ |   -13 After calculating B normally ? I mean by using mod at every step to calculate B?