Brackets12's blog

INVERSE MODULO FUNCTION? + Help explain>>>
By Brackets12, history, 6 hours ago, In English

I have seen some similar functions in problems where numbers are large and we need to mod a number like 998244353 or 1000000007 (I also noticed they are all prime). I think this function might be modular inverse??? But I don't know why any of this works and how do I use it. I don't get why I need to decrease 2 from the mod number to make it work. I don't get what the dividing by two is about. Will very appreciate if someone can help. Thank you. +++

1999F - Expected Median

const int N = 2e5 + 5, mod = 1e9 + 7;
int64_t fact[N];
int64_t pw(int64_t a, int64_t b) {
	int64_t r = 1;
	while(b > 0) {
		if(b & 1) r = (r * a) % mod;
		b /= 2;
		a = (a * a) % mod; 
	}
	return r;
}

2053D - Refined Product Optimality

int qpow(int a, int x = MOD — 2) {
	int res = 1;
	for (; x; x >>= 1, a = 1ll * a * a % MOD) if (x & 1) res = 1ll * res * a % MOD;
	return res;
}
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Brackets12 (previous revision, new revision, compare).

→ Reply
»
6 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

https://cses.fi/book/book.pdf#section.21.2

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This function simply quickly calculates $$$a^b$$$. It's the iterative version of:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD=1e9+7;

ll mpow(ll a, ll b){
    if(b==0) return 1;
    else if(b%2==0) return mpow((a*a)%MOD,b/2);
    else return (a*mpow((a*a)%MOD,b/2))%MOD;
}

This works because, if $$$b$$$ is even:

$$$a^b=a^{2\cdot\frac{b}{2}}=(a^2)^\frac{b}{2}$$$

And otherwise:

$$$a^b=a^{1+2\cdot\left\lfloor{\frac{b}{2}}\right\rfloor}=a\cdot(a^2)^\left\lfloor{\frac{b}{2}}\right\rfloor$$$

Modular inverse
The modular inverse of $a$ modulo $$$m$$$ is a number $$$a'$$$ so that $$$a\cdot a'\equiv1\pmod m$$$. This is useful in problems where you need to output the answer modulo some value, but need to divide it at some point.

If $$$m$$$ is prime, then:

$$$a'\equiv a^{m-2}\pmod m$$$

This can be proven using Fermat's little theorem:

$$$a^m\equiv a\pmod m\implies a^{m-2}\equiv a^{-1}\equiv\frac{1}{a}\pmod m$$$
→ Reply