Dados dos enteros A y B donde A no es divisible por B , la tarea es expresar A/B como un número natural módulo m donde m = 1000000007 .
Nota: esta representación es útil cuando necesitamos expresar la probabilidad de un evento, el área de curvas y polígonos, etc.
Ejemplos:
Entrada: A = 2, B = 6
Salida: 333333336
Entrada: A = 4, B = 5
Salida: 600000005
Enfoque: Sabemos que, A/B se puede escribir como A * (1/B), es decir , A * (B ^ -1) .
Se sabe que el operador módulo(%) satisface la relación:
(a * b) % m = ( (a % m) * (b % m) ) % m
Entonces, podemos escribir:
(b ^ -1) % m = (b ^ m-2) % m (Fermat's little theorem)
Por lo tanto el resultado será:
( (A mod m) * ( power(B, m-2) % m) ) % m
A continuación se muestra la implementación del enfoque anterior:
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 numbers int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Recursive function to return (x ^ n) % m 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); } } // Function to return the fraction modulo mod ll 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 code int main() { ll a = 2, b = 6; cout << getFractionModulo(a, b) << endl; return 0; }
Java
// Java implementation of the approach import 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) % m static 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 approach m = 1000000007 # Function to return the GCD # of given numbers def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # Recursive function to return (x ^ n) % m def 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 mod def 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 code if __name__ == "__main__": a = 2 b = 6 print ( getFractionModulo(a, b)) # This code is contributed by ita_c
C#
//C# implementation of the approach using System; public 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) % m static 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 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 numbers function abc($a, $b) { if ($a == 0) return $b; return abc($b % $a, $a); } // Recursive function to return (x ^ n) % m function 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 mod function 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>
Producción:
333333336
Complejidad de tiempo: O(log(min(a, b) + logm)
Espacio auxiliar: O(log(min(a, b) + logm)