Need your help friends,Codechef mod multiplication question.how to find a^b%mod c

help
,
1

I am reading the CodeChef Introductory Tutorials For Competitive Programming: Basic maths.(link:https://drive.google.com/file/d/0B-W-TWxgtybGRHdBRFdVT0ZraWc/view)
After reading the mod multiplication part we are expected to solve this question

Try writing a program to compute the 4 right-most digits of 2^10105 +
2^123456. Your output should be 3968.

Even after reading the text multiple time, I am not able to understand how we can solve the above problem. Please help me in understanding the concept and share your valuable tips with me.
Please do also tag your friends and other people who you think can share something to help.
I am thankful for any suggestion, advice, or study material you can share with me.
Thank you, my friends :smile:

2

( pow(2,10105,10000) + pow(2,123456,10000) ) % 10000

1 Like
3

“zTVKWe - Online Python3 Interpreter & Debugging Tool - Ideone.com”

4

I tried the exact same thing but i am getting error.(tried in C not this python function though)
Also isnt the number we get really big? doesnt it defeat the purpose of the concept they are teraching us.
thanks for your help

5

Lol, then u have to learn a^b mod p … Google it

7

“Modular Exponentiation (Power in Modular Arithmetic) - GeeksforGeeks”

1 Like
8

:sweat_smile: Actually I did that and browsed many websites but I am unable to understand how we can solve the question efficiently. Is the above Solution you posted an efficient one?

9

Yeah it is in python , same we do in c/cpp too…ok wait let me explain in some time , ur all doubts will be clear.

1 Like
10

you are really helpfull my friend. In the meantime I will again read about the article you shared and try to better understand the concept.
Also will it be fine if i ask you for help in the reply?

1 Like
11

You can calculate this quickly using a method known as fast exponentiation. The important fact is that b^{x+y}=b^x\cdot b^y. We will use the fact that every number can be represented as a sum of powers of two, it’s binary representation.

So as an example b^{13}=b^1\cdot b^4\cdot b^8

Here is the c++ code that would achieve that. Here Mod is a class I made myself that would take care of all modular arithmetic. ll is a type synonym I defined for long long.

Mod pow(Mod base, ll exp) {
	Mod ans = {1,base.mod};
	do {
		if (exp & 1) ans *= base;
		base *= base;
	} while (exp >>= 1);
	return ans;
}

The variable base iterates over b^1,b^2,b^4,b^8,\ldots. The exp >>=1 shifts the bits of the exponent one to the right and exp&1 checks if the rightmost bit is set to one.

If you were to implement this yourself make sure to always apply the modulo operator after each multiplication. Also make sure that base and ans are of type long long

2 Likes
12

Thanks a lot for the detailed answer i now seem to get the idea on the concept.
Actually i was reading about fast exponentiation but was not sure i was on the right track.
I will try to solve the question myself and share my progress with you all :smile: