Dados tres enteros positivos, P , Q y N , la tarea es encontrar el MCD de (P N + Q N ) y (P – Q) bajo módulo 10 9 + 7 .
Ejemplos:
Entrada: p = 10, q = 6, n = 5
Salida: 4
Explicación: p n + q n = 10 5 + 6 5 = 107776 y p – q = 4. MCD de 107776 y 4 es 4.Entrada: p =7, q = 2 y n = 5
Salida: 1
Explicación: p n + q n = 7 5 + 2 5 = 1.
Enfoque: dado que el número (p n + q n ) puede ser extremadamente grande, un número tan grande no se puede almacenar en ningún tipo de datos y, por lo tanto, GCD no se puede calcular utilizando el algoritmo euclidiano . Por lo tanto, la aritmética modular se puede utilizar para encontrar la respuesta.
Siga los pasos a continuación para resolver este problema:
- Para encontrar el MCD de un número grande y un número pequeño, encuentra los divisores del número más pequeño en O(√pq) .
- Estos números son los candidatos potenciales de GCD .
- Ahora, verifique si alguno de estos GCD potenciales divide el número más grande. El número más grande que divide a ambos números es la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
// Function to find the value of (a ^ n) % d
long long int power(long long a, long long n,
long long int d)
{
// Stores the value
// of (a ^ n) % d
long long int res = 1;
// Calculate the value
// of (a ^ n) % d
while (n) {
// If n is odd
if (n % 2) {
// Update res
res = ((res % d) * (a % d)) % d;
}
// Update a
a = ((a % d) * (a % d)) % d;
// Update n
n /= 2;
}
return res;
}
// Function to find the GCD of (p ^ n + q ^ n)
// and p - q mod d
long long int gcd(long long p, long long q,
long long n)
{
// If p and q are equal
if (p == q) {
return (power(p, n, mod)
+ power(q, n, mod))
% mod;
}
// Stores GCD of (p ^ n + q ^ n)
// and (p - q) mod d
long long int candidate = 1;
// Stores the value of (p-q)
long long int num = p - q;
// Stores square root of num
long long int sq = sqrt(num);
// Find the divisors of num.
for (long long i = 1; i <= sq; ++i) {
// If i divides num
if (num % i == 0) {
// Stores power of (p ^ n) mod i
long long int X = power(p, n, i);
// Stores power of (q ^ n) mod i
long long int Y = power(q, n, i);
// Stores power of (p ^ n + q ^ n) mod i
long long int temp = (X + Y) % i;
// If (p^n + q^n) is divisible by i
if (temp == 0) {
// Calculate the largest divisor.
candidate = max(candidate, i);
}
// If i divides num, (num/i) also divides
// num. Hence, calculate temp.
temp = (power(p, n, num / i)
+ power(q, n, num / i))
% (num / i);
// If (p^n + q^n) is divisible
// by (num/i)
if (temp == 0) {
// Calculate the largest divisor.
candidate = max(candidate, num / i);
}
}
}
return candidate % mod;
}
// Driver Code
int main()
{
// Given p, q and n
long long int p, q, n;
p = 10;
q = 6;
n = 5;
// Function Call
cout << gcd(p, q, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static int mod = 1000000007;
// Function to find the value of (a ^ n) % d
static int power(int a, int n, int d)
{
// Stores the value
// of (a ^ n) % d
int res = 1;
// Calculate the value
// of (a ^ n) % d
while (n != 0) {
// If n is odd
if ((n % 2) !=0) {
// Update res
res = ((res % d) * (a % d)) % d;
}
// Update a
a = ((a % d) * (a % d)) % d;
// Update n
n /= 2;
}
return res;
}
// Function to find the GCD of (p ^ n + q ^ n)
// and p - q mod d
static int gcd(int p, int q, int n)
{
// If p and q are equal
if (p == q) {
return (power(p, n, mod)
+ power(q, n, mod))
% mod;
}
// Stores GCD of (p ^ n + q ^ n)
// and (p - q) mod d
int candidate = 1;
// Stores the value of (p-q)
int num = p - q;
// Stores square root of num
int sq = (int)Math.sqrt(num);
// Find the divisors of num.
for (int i = 1; i <= sq; ++i) {
// If i divides num
if (num % i == 0) {
// Stores power of (p ^ n) mod i
int X = power(p, n, i);
// Stores power of (q ^ n) mod i
int Y = power(q, n, i);
// Stores power of (p ^ n + q ^ n) mod i
int temp = (X + Y) % i;
// If (p^n + q^n) is divisible by i
if (temp == 0) {
// Calculate the largest divisor.
candidate = Math.max(candidate, i);
}
// If i divides num, (num/i) also divides
// num. Hence, calculate temp.
temp = (power(p, n, num / i)
+ power(q, n, num / i))
% (num / i);
// If (p^n + q^n) is divisible
// by (num/i)
if (temp == 0) {
// Calculate the largest divisor.
candidate = Math.max(candidate, num / i);
}
}
}
return candidate % mod;
}
// Driver code
public static void main(String[] args)
{
// Given p, q and n
int p, q, n;
p = 10;
q = 6;
n = 5;
// Function Call
System.out.println(gcd(p, q, n));
}
}
// This code is contributed by code_hunt.
Python3
# Python program for the above approach import math mod = 1000000007; # Function to find the value of (a ^ n) % d def power(a, n, d): # Stores the value # of (a ^ n) % d res = 1; # Calculate the value # of (a ^ n) % d while (n != 0): # If n is odd if ((n % 2) != 0): # Update res res = ((res % d) * (a % d)) % d; # Update a a = ((a % d) * (a % d)) % d; # Update n n /= 2; return res; # Function to find the GCD of (p ^ n + q ^ n) # and p - q mod d def gcd(p, q, n): # If p and q are equal if (p == q): return (power(p, n, mod) + power(q, n, mod)) % mod; # Stores GCD of (p ^ n + q ^ n) # and (p - q) mod d candidate = 1; # Stores the value of (p-q) num = p - q; # Stores square root of num sq = (int)(math.sqrt(num)); # Find the divisors of num. for i in range(1, sq): # If i divides num if (num % i == 0): # Stores power of (p ^ n) mod i X = power(p, n, i); # Stores power of (q ^ n) mod i Y = power(q, n, i); # Stores power of (p ^ n + q ^ n) mod i temp = (X + Y) % i; # If (p^n + q^n) is divisible by i if (temp == 0): # Calculate the largest divisor. candidate = max(candidate, i); # If i divides num, (num/i) also divides # num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); # If (p^n + q^n) is divisible # by (num/i) if (temp == 0): # Calculate the largest divisor. candidate = max(candidate, num / i); return candidate % mod; # Driver code if __name__ == '__main__': # Given p, q and n p = 10; q = 6; n = 5; # Function Call print((int)(gcd(p, q, n))); # This code contributed by aashish1995
C#
// C# program for the above approach
using System;
class GFG
{
static int mod = 1000000007;
// Function to find the value of (a ^ n) % d
static int power(int a, int n, int d)
{
// Stores the value
// of (a ^ n) % d
int res = 1;
// Calculate the value
// of (a ^ n) % d
while (n != 0)
{
// If n is odd
if ((n % 2) != 0)
{
// Update res
res = ((res % d) * (a % d)) % d;
}
// Update a
a = ((a % d) * (a % d)) % d;
// Update n
n /= 2;
}
return res;
}
// Function to find the GCD of (p ^ n + q ^ n)
// and p - q mod d
static int gcd(int p, int q, int n)
{
// If p and q are equal
if (p == q)
{
return (power(p, n, mod) + power(q, n, mod))
% mod;
}
// Stores GCD of (p ^ n + q ^ n)
// and (p - q) mod d
int candidate = 1;
// Stores the value of (p-q)
int num = p - q;
// Stores square root of num
int sq = (int)Math.Sqrt(num);
// Find the divisors of num.
for (int i = 1; i <= sq; ++i) {
// If i divides num
if (num % i == 0) {
// Stores power of (p ^ n) mod i
int X = power(p, n, i);
// Stores power of (q ^ n) mod i
int Y = power(q, n, i);
// Stores power of (p ^ n + q ^ n) mod i
int temp = (X + Y) % i;
// If (p^n + q^n) is divisible by i
if (temp == 0) {
// Calculate the largest divisor.
candidate = Math.Max(candidate, i);
}
// If i divides num, (num/i) also divides
// num. Hence, calculate temp.
temp = (power(p, n, num / i)
+ power(q, n, num / i))
% (num / i);
// If (p^n + q^n) is divisible
// by (num/i)
if (temp == 0) {
// Calculate the largest divisor.
candidate
= Math.Max(candidate, num / i);
}
}
}
return candidate % mod;
}
// Driver code
static public void Main()
{
// Given p, q and n
int p, q, n;
p = 10;
q = 6;
n = 5;
// Function Call
Console.WriteLine(gcd(p, q, n));
}
}
// This is contributed by Dharanendra L V
Javascript
<script>
// javascript program for the above approach
const mod = 1000000007;
// Function to find the value of (a ^ n) % d
function power(a , n , d) {
// Stores the value
// of (a ^ n) % d
var res = 1;
// Calculate the value
// of (a ^ n) % d
while (n != 0) {
// If n is odd
if ((n % 2) != 0) {
// Update res
res = ((res % d) * (a % d)) % d;
}
// Update a
a = ((a % d) * (a % d)) % d;
// Update n
n /= 2;
}
return res;
}
// Function to find the GCD of (p ^ n + q ^ n)
// and p - q mod d
function gcd(p , q , n)
{
// If p and q are equal
if (p == q)
{
return (power(p, n, mod) + power(q, n, mod)) % mod;
}
// Stores GCD of (p ^ n + q ^ n)
// and (p - q) mod d
var candidate = 1;
// Stores the value of (p-q)
var num = p - q;
// Stores square root of num
var sq = parseInt( Math.sqrt(num));
// Find the divisors of num.
for (i = 1; i <= sq; ++i) {
// If i divides num
if (num % i == 0) {
// Stores power of (p ^ n) mod i
var X = power(p, n, i);
// Stores power of (q ^ n) mod i
var Y = power(q, n, i);
// Stores power of (p ^ n + q ^ n) mod i
var temp = (X + Y) % i;
// If (p^n + q^n) is divisible by i
if (temp == 0) {
// Calculate the largest divisor.
candidate = Math.max(candidate, i);
}
// If i divides num, (num/i) also divides
// num. Hence, calculate temp.
temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i);
// If (p^n + q^n) is divisible
// by (num/i)
if (temp == 0) {
// Calculate the largest divisor.
candidate = Math.max(candidate, num / i);
}
}
}
return candidate % mod;
}
// Driver code
// Given p, q and n
var p, q, n;
p = 10;
q = 6;
n = 5;
// Function Call
document.write(gcd(p, q, n));
// This code is contributed by todaysgaurav
</script>
Producción:
4
Complejidad de tiempo: O(sqrt(p – q))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA