Expressing a fraction as a natural number under modulo ' m ' | C ++ implementation of the approach ; Function to return the GCD of given numbers ; Recursive function to return ( x ^ n ) % m ; Function to return the fraction modulo mod ; ( b ^ m - 2 ) % m ; Final answer ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE #define m  1000000007 NEW_LINE int gcd ( int a , int b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } ll modexp ( ll x , ll n ) { if ( n == 0 ) { return 1 ; } else if ( n % 2 == 0 ) { return modexp ( ( x * x ) % m , n / 2 ) ; } else { return ( x * modexp ( ( x * x ) % m , ( n - 1 ) / 2 ) % m ) ; } } ll getFractionModulo ( ll a , ll b ) { ll c = gcd ( a , b ) ; a = a / c ; b = b / c ; ll d = modexp ( b , m - 2 ) ; ll ans = ( ( a % m ) * ( d % m ) ) % m ; return ans ; } int main ( ) { ll a = 2 , b = 6 ; cout << getFractionModulo ( a , b ) << endl ; return 0 ; }