Calculate A^B mod C

A <= 10^100000

B <= 10^100000

C <= 10^9 (Doesn't have to be a prime number)

Thanks :)).

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 143 |

Calculate A^B mod C

A <= 10^100000

B <= 10^100000

C <= 10^9 (Doesn't have to be a prime number)

Thanks :)).

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2023 12:37:40 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The constraints on A and B seem quite large, but the way would be:

Note that (a^b)%c = ((a%c)^b)%c so,

1) Compute (a%c)

2) Use binary exponentiation to compute ((a%c)^b)%c in log(10^100000) time

In python, integers are infinite so u can directly calculate a%c and pow function implements binary exponentiation, so the ans would be simply pow(a%c,b,c).

In C++, where u have no bigint by default, u can input 'a' as a string, and do as follows:

As for binary exponentiation you would need to input b as a string and convert it to a binary string. And then instead of the while(b>0) and b/=2 in the regular binary exponentiation, traverse b in the reverse order replacing the if condition (b%2==1) with b[i]=='1'.

Oh thanks. I was looking for a mathematical approach for B but converting it into binary would work too :))

Wait, but converting a number into binary would take log10(n) * log2(n) which would TLE in this case, right?

No it will take only log2(b). Precisely I think you meant inputting as a string takes log10(b) and converting takes log2(b), so the total time taken is log10(b)+log2(b), not log10(b)*log2(b)

How would you impmement big integer base conversion in $$$O(n)$$$ (where $$$n$$$ is the length of the integer to be converted)? Because I'm quite sure that it is not possible. The best I could find was $$$O(n \log^2 n)$$$ described here.

But technically we don't need to convert the base of $$$B$$$, we can instead use a modified version of binary exponentiation that goes one digit at a time on the base 10 representation and does up to 20 single multiplications on each step. If you don't understand my idea, I can add a code snippet of my method.

UPD:

CodeThat would be great! I have never heard of that variation of binary exponentiation

I updated my previous comment with the code.

I haven't heard of it either; I just came up with it because it was an easy way to solve your problem.

My solution is coded iteratively and not recursively. It relies on the same idea as typical binary exponentiation, just in base 10:

Suppose $$$B = 12345$$$.

Now, $$$A^B = A^{12345}$$$

$$$= A^{12340} \cdot A^{5}$$$

$$$= (A^{1234})^{10} \cdot A^{5}$$$

and now we can calculate $$$A^{1234}$$$ recursively using the same method. But instead of doing recursion, I implemented the same thing iteratively starting from the other end.

Now that I think about it, you could also do it recursively like this:

CodeYes, and beware: python

`int()`

function runs in quadraticYes sorry... really have got into the bad habit of not considering logarithms sometimes.... 'Cause they generally they don't matter too much in cp solutions (I mean questions giving AC in O(n) mostly give AC in O(nlogn) too as n is generally upto 1e5 or 1e6).

But thanks for the clarification

ok.

Look at constraints

First the input will be taken as string.

Convery the given numbers in binary then take xor

Iterate through the string and and at each step remainder can be calculated as

Code snippetlets reminder be ans and string obtain after taking xor be s and C from which mod have to be taken

for(int i = 0; i < s.size(); i++) {

ans = (ans * 10 + s[i] — '0') % C;

}

public static int power(long x, long y, long p) { long res = 1;

If $$$B<\phi(C)$$$ then $$$A^B \bmod C = (A \bmod C)^{B} \bmod C$$$

If $$$B≥\phi(C)$$$ then $$$A^B \bmod C = (A \bmod C)^{\phi(C) + (B \bmod \phi(C))} \bmod C$$$

$$$\phi$$$ here denotes the euler toient function

The above is true for All $$$C$$$

You can calculate :

$$$\phi(C)$$$ in $$$O(\sqrt C)$$$

$$$A \bmod C$$$ in $$$O(\log_{10}A)$$$

$$$B \bmod \phi(C)$$$ in $$$O(\log_{10}B)$$$ with also determining whether $$$B<\phi(C)$$$ or $$$B≥\phi(C)$$$

$$$A^B \bmod C$$$ in $$$O(\log_{2}\phi(C))$$$ using the new information above

Thanks! It works :))

You are welcome