Given two integers A and B where A is not divisible by B, the task is to express A / B as a natural number modulo m where m = 1000000007.
Note: This representation is useful where we need to express Probability of an event, Area of Curves and polygons etc.
Examples:
Input: A = 2, B = 6
Output: 333333336
Input: A = 4, B = 5
Output: 600000005
Approach: We know that, A / B can be written as A * (1 / B) i.e. A * (B ^ -1).
It is known that the modulo(%) operator satisfies the relation:
(a * b) % m = ( (a % m) * (b % m) ) % m
So, we can write:
(b ^ -1) % m = (b ^ m-2) % m (Fermat's little theorem)
Therefore the result will be:
( (A mod m) * ( power(B, m-2) % m) ) % m
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long int#define m 1000000007// Function to return the GCD of given numbersint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Recursive function to return (x ^ n) % mll 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); }}// Function to return the fraction modulo modll getFractionModulo(ll a, ll b){ ll c = gcd(a, b); a = a / c; b = b / c; // (b ^ m-2) % m ll d = modexp(b, m - 2); // Final answer ll ans = ((a % m) * (d % m)) % m; return ans;}// Driver codeint main(){ ll a = 2, b = 6; cout << getFractionModulo(a, b) << endl; return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { static long m = 1000000007;// Function to return the GCD of given numbers static long gcd(long a, long b){ if (a == 0) return b; return gcd(b % a, a);}// Recursive function to return (x ^ n) % mstatic long modexp(long x, long 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); }}// Function to return the fraction modulo mod static long getFractionModulo(long a, long b){ long c = gcd(a, b); a = a / c; b = b / c; // (b ^ m-2) % m long d = modexp(b, m - 2); // Final answer long ans = ((a % m) * (d % m)) % m; return ans;}// Driver code public static void main (String[] args) { long a = 2, b = 6; System.out.println(getFractionModulo(a, b)); }}// This code is contributed by inder_verma |
Python3
# Python3 implementation of the approachm = 1000000007# Function to return the GCD # of given numbersdef gcd(a, b): if (a == 0): return b return gcd(b % a, a)# Recursive function to return (x ^ n) % mdef modexp(x, n): if (n == 0) : return 1 elif (n % 2 == 0) : return modexp((x * x) % m, n // 2) else : return (x * modexp((x * x) % m, (n - 1) / 2) % m)# Function to return the fraction modulo moddef getFractionModulo(a, b): c = gcd(a, b) a = a // c b = b // c # (b ^ m-2) % m d = modexp(b, m - 2) # Final answer ans = ((a % m) * (d % m)) % m return ans# Driver codeif __name__ == "__main__": a = 2 b = 6 print ( getFractionModulo(a, b))# This code is contributed by ita_c |
C#
//C# implementation of the approachusing System;public class GFG{ static long m = 1000000007;// Function to return the GCD of given numbersstatic long gcd(long a, long b){ if (a == 0) return b; return gcd(b % a, a);}// Recursive function to return (x ^ n) % mstatic long modexp(long x, long 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); }}// Function to return the fraction modulo modstatic long getFractionModulo(long a, long b){ long c = gcd(a, b); a = a / c; b = b / c; // (b ^ m-2) % m long d = modexp(b, m - 2); // Final answer long ans = ((a % m) * (d % m)) % m; return ans;}// Driver code static public void Main (){ long a = 2, b = 6; Console.WriteLine(getFractionModulo(a, b)); }} |
PHP
<?php// PHP implementation of the approach// Function to return the GCD of// given numbersfunction abc($a, $b){ if ($a == 0) return $b; return abc($b % $a, $a);}// Recursive function to return (x ^ n) % mfunction modexp($x, $n){ $m = 1000000007; 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); }}// Function to return the fraction// modulo modfunction getFractionModulo($a, $b){ $m = 1000000007; $c = abc($a, $b); $a = $a / $c; $b = $b / $c; // (b ^ m-2) % m $d = modexp($b, $m - 2); // Final answer $ans = (($a % $m) * ($d % $m)) % $m; return $ans;}// Driver code$a = 2;$b = 6;echo(getFractionModulo($a, $b)) ;// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// javascript implementation of the approach var m = 100000007; // Function to return the GCD of given numbers function gcd(a , b) { if (a == 0) return b; return gcd(b % a, a); } // Recursive function to return (x ^ n) % m function modexp(x , 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); } } // Function to return the fraction modulo mod function getFractionModulo(a , b) { var c = gcd(a, b); a = a / c; b = b / c; // (b ^ m-2) % m var d = modexp(b, m - 2); // Final answer var ans = ((a % m) * (d % m)) % m; return ans; } // Driver code var a = 2, b = 6; document.write(getFractionModulo(a, b));// This code is contributed by umadevi9616</script> |
333333336
Time Complexity: O(log(min(a, b) + logm)
Auxiliary Space: O(log(min(a, b) + logm)
Approach#2: Using fermat’s little
This approach computes the value of (A/B) % m using Fermat’s Little Theorem to calculate the modular inverse of B.
Algorithm
1. Define a function inverse_modulo(a, m) to compute the inverse of a modulo m using Fermat’s Little Theorem.
2. Define a function fraction_to_natural_modulo(A, B, m) to compute the value of (A/B) % m, where A, B, and m are given integers.
3. Inside the fraction_to_natural_modulo function, calculate the inverse of B modulo m using the inverse_modulo function.
4. Multiply A and the inverse of B modulo m, and take modulo m to get the result.
5. Return the result
Python3
def inverse_modulo(a, m): """ Computes the inverse of a modulo m using Fermat's Little Theorem """ return pow(a, m-2, m)def fraction_to_natural_modulo(A, B, m): """ Computes the value of (A/B) % m, where A, B and m are given integers """ inverse_B = inverse_modulo(B, m) result = (A * inverse_B) % m return result# Example usageA = 2B = 6m = 1000000007natural_number = fraction_to_natural_modulo(A, B, m)print(natural_number) |
333333336
Time complexity:
The time complexity of this code is O(log m) because it uses the pow() function to compute the inverse modulo.
Auxiliary Space:
The space complexity of this code is O(1) because it only stores a few integers in memory.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
