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)