How to calculate (a power b) mod p correctly if b is exceeding long long integer limit in c++.

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

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

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

1 | Um_nik | 185 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 153 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

How to calculate (a power b) mod p correctly if b is exceeding long long integer limit in c++.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/02/2023 00:28:20 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

O(log2(b))?

yup!

Let b = b1b2.....bn(concatenated) By induction, Let x = a ^ (b1b2...bk) (mod p)

a ^ (b1b2....b(k+1)) = ( a^(b1b2....bk) ) ^ 10 * (a ^ b(k+1)) = x^10 * a^b(k+1)

now you can calculate modulo without overflow

got it! Thanks

first i need to store b. But b is exceeding the integer limit! How can i store b so that i correctly calculate (a power b) mod p. p is prime.

If

bis in the form of a string, then we can calculate with the following code:Now assuming that

ais nonzero.EDIT: This is exactly what DongwonShin wrote above. If

bis being calculated via a DP table, then you can just take all values modp- 1 and there won't be overflow.got it. thanks!

but why p-1?

Fermat's theorem tells us that if (

a,p) = 1. So we can take the power by the modulo.Thanks man!

In general if you have two co prime integers m and n, then m^p modulo n = m^(p%f(n)) modulo n, where f(n) is Euler totient function This.

For any prime n, f(n)=n-1.So, the Fermat's theorem follows from this.

I am using precomputed factorial and inverse factorial array to calculate b so should i use n-1 as the mod there also?

What if b is being calculated through nCr using precomputed factorial and inverse modulo arrays?Then also we've to use same mod p-1 ?

As long as your base(b) and p are co prime, I don't see why it can't be done. So, yes use same mod (p-1).

I tried but then for example 11*(inv[11)) didn't turn out to be 1 when i used p-1 as mod but while using p as mod it did show 1. here inv[11] = power(11,mod-2,mod) where power is fast exponential function.

What if b is calculated as a-c and c requires division operation?Then while using inverse modulo for division i should use which mod?I am confused.Please help.

Refer https://www.geeksforgeeks.org/find-abm-where-b-is-very-large/