Dado el primer término (A) y diferencia común (D) de una Progresión Aritmética, y un número primo (P). La tarea es encontrar la posición del primer elemento en el AP dado que es un múltiplo del número primo P dado.
Ejemplos :
Entrada : A = 4, D = 9, P = 11
Salida : 2
Explicación :
El tercer término del AP dado es
un múltiplo del número primo 11.
Primer término = 4
Segundo término = 4+9 = 13
Tercer término = 4+ 2*9 = 22
Entrada : A = 5, D = 6, P = 7
Salida : 5
Explicación :
El sexto término del AP dado es
un múltiplo del número primo 7.
Primer término = 5
Segundo término = 5+6 = 11
Tercer Término = 5+2*6 = 17
Cuarto Término = 5+3*6 = 23
Quinto Término = 5+4*6 = 29
Sexto Término = 5+5*5 = 35
Enfoque:
Sea el término A N . Por lo tanto,
AN = (A + (N-1)*D)
Ahora, se da que A N es múltiplo de P. Entonces,
A + (N-1)*D = k*P Where, k is a constant.
Ahora sea A (A % P) y D (D % P). Entonces, tenemos (N-1)*D = (k*P – A).
Sumando y restando P en RHS, obtenemos:
(N-1)*D = P(k-1) + (P-A), Where P-A is a non-negative number (since A is replaced by A%P which is less than P)
Finalmente tomando mod en ambos lados:
((N-1)*D)%P = (P-A)%P or, ((N-1)D)%P = P-A
Encontremos un X < P, tal que (D*X)%P = 1. Este X se conoce como el módulo inverso de D con respecto a P.
Por lo tanto, la respuesta N es:
((X*(P-A)) % P) + 1.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Iterative Function to calculate
// (x^y)%p in O(log y) */
int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// function to find nearest element in common
int NearestElement(int A, int D, int P)
{
// base conditions
if (A == 0)
return 0;
else if (D == 0)
return -1;
else {
int X = power(D, P - 2, P);
return (X * (P - A)) % P;
}
}
// Driver code
int main()
{
int A = 4, D = 9, P = 11;
// module both A and D
A %= P;
D %= P;
// function call
cout << NearestElement(A, D, P);
return 0;
}
C
#include <stdio.h>
// Iterative Function to calculate
// (x^y)%p in O(log y) */
int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// function to find nearest element in common
int NearestElement(int A, int D, int P)
{
// base conditions
if (A == 0)
return 0;
else if (D == 0)
return -1;
else {
int X = power(D, P - 2, P);
return (X * (P - A)) % P;
}
}
// Driver code
int main()
{
int A = 4, D = 9, P = 11;
// module both A and D
A %= P;
D %= P;
// function call
printf("%d",NearestElement(A, D, P));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java Program to Find First
// element in AP which is
// multiple of given prime
class GFG
{
// Iterative Function to
// calculate (x^y)%p in
// O(log y) */
static int power(int x,
int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is
// more than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) != 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// function to find nearest
// element in common
static int NearestElement(int A,
int D, int P)
{
// base conditions
if (A == 0)
return 0;
else if (D == 0)
return -1;
else
{
int X = power(D, P - 2, P);
return (X * (P - A)) % P;
}
}
// Driver code
public static void main(String args[])
{
int A = 4, D = 9, P = 11;
// module both A and D
A %= P;
D %= P;
// function call
System.out.println(NearestElement(A, D, P));
}
}
// This code is contributed
// by Arnab Kundu
Python 3
# Python 3 Program to Find First # element in AP which is # multiple of given prime # Iterative Function to calculate # (x^y)%p in O(log y) def power(x, y, p) : # Initialize result res = 1 # Update x if it is more than or # equal to p x = x % p while y > 0 : # If y is odd, multiply x with result if y & 1 : res = (res * x) % p # y must be even now # y = y/2 y = y >> 1 x = (x * x) % p return res # function to find nearest element in common def NearestElement(A, D, P) : # base conditions if A == 0 : return 0 elif D == 0 : return -1 else : X = power(D, P - 2, P) return (X * (P - A)) % P # Driver Code if __name__ == "__main__" : A, D, P = 4, 9, 11 # module both A and D A %= P D %= P # function call print(NearestElement(A, D, P)) # This code is contributed by ANKITRAI1
C#
// C# Program to Find First
// element in AP which is
// multiple of given prime
using System;
class GFG
{
// Iterative Function to
// calculate (x^y)%p in
// O(log y) */
static int power(int x,
int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is
// more than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) != 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// function to find nearest
// element in common
static int NearestElement(int A,
int D, int P)
{
// base conditions
if (A == 0)
return 0;
else if (D == 0)
return -1;
else
{
int X = power(D, P - 2, P);
return (X * (P - A)) % P;
}
}
// Driver code
public static void Main()
{
int A = 4, D = 9, P = 11;
// module both A and D
A %= P;
D %= P;
// function call
Console.WriteLine(NearestElement(A, D, P));
}
}
// This code is contributed
// by chandan_jnu.
PHP
<?php
// Iterative Function to calculate
// (x^y)%p in O(log y) */
function power($x, $y, $p)
{
// Initialize result
$res = 1;
// Update x if it is more
// than or equal to p
$x = $x % $p;
while ($y > 0)
{
// If y is odd, multiply
// x with result
if ($y & 1)
$res = ($res * $x) %$p;
// y must be even now
$y = $y >> 1; // y = y/2
$x = ($x * $x) %$p;
}
return $res;
}
// function to find nearest
// element in common
function NearestElement($A, $D, $P)
{
// base conditions
if ($A == 0)
return 0;
else if ($D == 0)
return -1;
else
{
$X = power($D, $P - 2, $P);
return ($X * ($P - $A)) %$P;
}
}
// Driver code
$A = 4; $D = 9; $P = 11;
// module both A and D
$A %= $P;
$D %= $P;
// function call
echo NearestElement($A, $D, $P);
// This code is contributed
// by chandan_jnu.
?>
Javascript
<script>
// Javascript Program to Find First
// element in AP which is
// multiple of given prime
// Iterative Function to
// calculate (x^y)%p in
// O(log y) */
function power(x, y, p)
{
// Initialize result
let res = 1;
// Update x if it is
// more than or equal to p
x = x % p;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) != 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// function to find nearest
// element in common
function NearestElement(A, D, P)
{
// base conditions
if (A == 0)
return 0;
else if (D == 0)
return -1;
else
{
let X = power(D, P - 2, P);
return (X * (P - A)) % P;
}
}
// driver program
let A = 4, D = 9, P = 11;
// module both A and D
A %= P;
D %= P;
// function call
document.write(NearestElement(A, D, P));
</script>
Producción:
2
Complejidad del tiempo: O(log y)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA