Problem Statement

Write a code calculate the inverse modulo of an integer.

Solution

Inverse modulo of a number is the number raised to mod-2 power, where mod is number w.r.t. which we have to take the inverse. Hence writing an efficient exponentiation function is enough.

Complexity

Fast exponentiation can be done in O(log(e)) where e is the exponent. It uses the binary expansion of the exponent.

Code

https://ideone.com/QG5MZe

Code

#include <iostream>
using namespace std;
int mod = 1000000007;
long long exp(int b, int e){
	long long a = 1;
	long long x = b;
	while(e){
		if(e%2)	a = (a*x)%mod;
		x = (x*x)%mod;
		e = e/2;
	}
	return a;
}
long long inv(int n){
	return exp(n,mod-2);
}
int main() {
	cout<<inv(12);
	return 0;
}

Ideone it!