Encuentre el primer elemento en AP que es múltiplo del primo dado

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *