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

×

# How to calculate (a ^ b) % c

 2 6 Could anyone give me a hint how to calculate (a ^ b) % c (with 2 <= a < 10^1000000, 1 <= b < 10^1000000, 2 <= c <= 10^9)? I try to use this formula (a ^ b) % c = ((a % c) ^ (b % phi(c)) % c (phi(c) is Euler's totient). But I realize that a and c aren't coprime. Is it necessary that a and c must be coprime? Or we must use other formula. Thank you! ^-^ asked 05 Nov '14, 09:18 33●2●1●5 accept rate: 0% Can you provide a link to the problem? (06 Nov '14, 10:04) The language for above problem is Vietnamese, do you want to get the link? (06 Nov '14, 17:15)

 2 Yes a and c should be coprime to use this formula. You can break c into prime powers. Compute the answer modulo p^k where p is prime. Now after doing this, you can use CRT to combine the answers using CRT. answered 05 Nov '14, 09:26 2.5k●53●137●170 accept rate: 20% Could you tell me more about that? ^^ (05 Nov '14, 09:29) Yes certainly, I have some meeting to do in around 3 hours. I will explain it in detail after that. (05 Nov '14, 09:30) Thank you very much :D (05 Nov '14, 09:36) I have added small explanation. (05 Nov '14, 10:15)
 2 You can learn CRT mostly from it's wikipedia article. Break General modulo into prime power modulo's A summary: Basically when we have to compute something modulo n where n is not prime, according to this theorem, we can break this kind of questions into cases where the number by which you are taking modulo's is a prime power. This can be done by write n in its prime representation n = p1q1. . . pkqk Compute modulo p^k by usual methods Many times we can use standard tricks to find answer modulo p^k. Merge those answers After getting modulo p^k answers, we can merge them using CRT. For that see the example given in the wikipedia page. Short Example Compute a^b % n assume a = 4 and n = 6. Write n = 6 = 2 * 3 Compute a^b % 2 = 0 Compute a^b % 3 = 1 Now merge them using CRT. See the formula given in the wikipedia to merge it. Details of Merging Assume we want to find a % n. Let n = p1 * p2. Find a % p1 and a % p2. Call a % p1 = x1 Call a % p2 = x2; For finding a % n. We can do following. Write a % n = x1 * alpha1 + x2 * alpha2; (Proof is very simple). where alpha1 is such that alpha1 = 1 mod p1 and alpha1 = 0 mod p2 Similarly define alpha2 where alpha1 is such that alpha2 = 0 mod p1 and alpha2 = 1 mod p2 So basically find alpha1, alpha2. For finding these, you need to solve two equations of two variables. That can be done by simplifying the equations written above. Finally your answer will x1 * alpha1 + x2 * alpha2. Sample Implementation See the following code answered 05 Nov '14, 10:14 2.5k●53●137●170 accept rate: 20% sir can you please explain the constructive algorithm of CRT...I am unable to get it from the example given in wiki link..thank you in advance (05 Nov '14, 14:15) 1 Ohk, its not that hard actually. It can be derived easily. I am writing the derivation in the modified answer. (05 Nov '14, 16:13) That is very nice method. This is the first time I've read it. Thank you very much! :D (05 Nov '14, 20:39) My friend! I have a question. If a and c aren't coprime, it means that there is a prime (let it is pi) that a % pi == 0 && c % pi == 0, and pi is in the set of prime (we break c), and when we apply above formula, we can't calculate value of ((a % pi) ^ (b % phi(pi))) % pi (because gcd(a, pi) > 1) (after calculate, we can use CRT to calculate the answer). Could you tell me more about that? Thank you in advance :D (06 Nov '14, 16:42) 1 if a % p = 0, then a^n % p will always be zero. (07 Nov '14, 19:08) Oh :D, thank you :D (08 Nov '14, 08:50) showing 5 of 6 show all
 0 I usually use a function to calculate it, by divide b into two part, and continue to do that in same function with b' = b/2 (called "backtrack"). Pseudo code: func pow( int a, int b, int c) { If b=1 then exit with a%c; //Divide b by 2: pow = (pow (a, b/2, c) * (pow(a, b/2, c)) mod c; //Case b is odd: pow = (pow*a) mod c; }  That code I wrote depend on C++. You can change it into other languages, using quotes. p.s: You are Vietnamese, right? I'm in Vung Tau. upd1: I am not sure that what time limit of your problem is, but with b = 10000000000000000000000000000000000000000, if consumes about O(logb) ~ O(132), and I think that it could work with b <= 10^1000000. upd2: a/b means that a div b. answered 05 Nov '14, 09:30 125●2●8 accept rate: 16% Yes, I'm in Hue ^^. But b is really huge, 1 <= b < 10^1000000, how can we apply this code with that b. Time limit is 1s. (05 Nov '14, 09:35) I use C++ too :D (05 Nov '14, 09:38) Hm... With b, you must use array or string to store it. Imagine that if a = 10^1000000, b=10^1000000, and c = 2, then how can you calculator (10^1000000 % 2) * (10^1000000 % phi(2))?? (05 Nov '14, 09:47) I store a in a string s = a1a2a3...an (n is length of a) Then I use this formula a%c = (a1 * 10^(n-1) % c + a2 * 10^(n-2) % c + ... + an * 1 % c) % c (05 Nov '14, 09:52) Don't you think your if-else ladder for even exponent is very inefficient ? (18 Jul '16, 22:41)
 0 Why don't you use simple modular exponentiation? long long square(long long x) { return (x*x)%MOD;
 } long long power(long long base,long long expo) { if(base==0) return 0; if(expo==0) return 1; else { if(expo%2==0) return square(power(base,expo/2))%MOD; else return (base*power(base,expo-1))%MOD; } } Here base is a, expo is b and MOD is c. answered 05 Nov '14, 21:35 893●2●11●35 accept rate: 10% Like my opinion, but, limitation of b is 10^1000000, so that function can't work in 1s. Total consumption: O(n*log2(10^n)), n=10^6. (05 Nov '14, 23:24) Can you tell me the question requiring it please? (06 Nov '14, 10:04) I don't know the question requiring, just understand that: "calculate a^b % c " :D (07 Nov '14, 07:40)
 0 Use logarithmic exponentiation Here is the c++ implimentation int power(int a,int b){ long long x=1; while(b){ if(b&1){ x=a; x%=mod; } a=a; a%=mod; b>>=1; } return x; } answered 06 Nov '14, 22:01 1.0k●1●13 accept rate: 4%
 0 Hi, just check 《Introduction to Algorithms, 3rd Edition》Chapter 31.6. Especially "Raising to powers with repeated squaring" section In order to calculate a^b(mod n): MODULAR-EXPONENTIATION(a, b, n) c = 0 d =1 let be the binary representation of b for i = k downto 0 c = 2c d = (d * d) mod n if (bi == 1) c = c + 1 d = (d * a) mod n return d  answered 09 Sep '18, 03:48 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×12

question asked: 05 Nov '14, 09:18

question was seen: 9,004 times

last updated: 18 Jul '16, 22:41