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

tonthatvinh's gravatar image

4★tonthatvinh
33215
accept rate: 0%

Can you provide a link to the problem?

(06 Nov '14, 10:04) dragonemperor3★

The language for above problem is Vietnamese, do you want to get the link?

(06 Nov '14, 17:15) tonthatvinh4★

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.

link

answered 05 Nov '14, 09:26

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 05 Nov '14, 09:33

Could you tell me more about that? ^^

(05 Nov '14, 09:29) tonthatvinh4★

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) dpraveen ♦♦4★

Thank you very much :D

(05 Nov '14, 09:36) tonthatvinh4★

I have added small explanation.

(05 Nov '14, 10:15) dpraveen ♦♦4★

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

link

answered 05 Nov '14, 10:14

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 05 Nov '14, 16:21

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) tanaymathur42★
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) dpraveen ♦♦4★

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

(05 Nov '14, 20:39) tonthatvinh4★

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) tonthatvinh4★
1

if a % p = 0, then a^n % p will always be zero.

(07 Nov '14, 19:08) dpraveen ♦♦4★

Oh :D, thank you :D

(08 Nov '14, 08:50) tonthatvinh4★
showing 5 of 6 show all

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.

link

answered 05 Nov '14, 09:30

leduongtuananh's gravatar image

2★leduongtuananh
12528
accept rate: 16%

edited 05 Nov '14, 09:35

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

I use C++ too :D

(05 Nov '14, 09:38) tonthatvinh4★

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

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

Don't you think your if-else ladder for even exponent is very inefficient ?

(18 Jul '16, 22:41) shubham992★

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.

link

answered 05 Nov '14, 21:35

dragonemperor's gravatar image

3★dragonemperor
89321135
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) leduongtuananh2★

Can you tell me the question requiring it please?

(06 Nov '14, 10:04) dragonemperor3★

I don't know the question requiring, just understand that: "calculate a^b % c " :D

(07 Nov '14, 07:40) leduongtuananh2★

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

link

answered 06 Nov '14, 22:01

rajat1603's gravatar image

7★rajat1603
1.0k113
accept rate: 4%

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 <bk,bk-1,...,b0> 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
link

answered 09 Sep '18, 03:48

aimsecond's gravatar image

0★aimsecond
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Related questions