×

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)
 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

By Email:

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