How to calculate (a ^ b) % c

general
1

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 (phi© 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! ^-^

2 Likes
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.

2 Likes
3

Could you tell me more about that? ^^

4

Yes certainly, I have some meeting to do in around 3 hours. I will explain it in detail after that.

5

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.

6

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.

7

Thank you very much :smiley:

8

I use C++ too :smiley:

9

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

10

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

11

You can learn CRT mostly from [it’s wikipedia article][1].

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


[2]

[1]: http://en.wikipedia.org/wiki/Chinese_remainder_theorem
[2]: http://stanford.edu/~liszt90/acm/notebook.html#file13
2 Likes
12

I have added small explanation.

13

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

14

Ohk, its not that hard actually. It can be derived easily.
I am writing the derivation in the modified answer.

1 Like
15

That is very nice method. This is the first time I’ve read it. Thank you very much! :smiley:

16

Why don’t you use simple modular exponentiation?

long long square(long long x)
{

return (x*x)%MOD;</br>

}
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.

17

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.

18

Can you tell me the question requiring it please?

19

Can you provide a link to the problem?

20

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 :smiley: