Número de pares de líneas que tienen puntos de intersección enteros

Dadas dos arrays de enteros P[] y Q[] , donde p _i y q _j para cada 0 <= i < tamaño (P) y 0 <= j < tamaño (Q) representan las ecuaciones de línea x – y = -p _i y x + y = _qj respectivamente. La tarea es encontrar el número de pares de P[] y Q[] que tienen puntos de intersección enteros.

Ejemplos: 

Entrada: P[] = {1, 3, 2}, Q[] = {3, 0} 
Salida: 3 
Los pares de líneas (p, q) que tienen puntos de intersección enteros son (1, 3), (2, 0) ) y (3, 3). Aquí p es el parámetro de línea de P[] y q es el de Q[].

Entrada: P[] = {1, 4, 3, 2}, Q[] = {3, 6, 10, 11} 
Salida: 8 
 

Acercarse:  

• El problema se puede resolver fácilmente resolviendo las dos ecuaciones y analizando la condición de los puntos de intersección de enteros.
• Las dos ecuaciones son x – y = -p y x + y = q .
• Resolviendo para x e y obtenemos, x = (qp)/2 y y = (p+q)/2 .
• Está claro que el punto de intersección de enteros es posible si y solo si p y q tienen la misma paridad.
• Sean p ₀ y p ₁ el número de pares e impares p _i respectivamente.
• De manera similar, q ₀ y q ₁ para el número de pares e impares q _i respectivamente.
• Por lo tanto, las respuestas requeridas son p ₀ * q ₀ + p ₁ * q ₁ .

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to Number of pairs of lines
// having integer intersection points
 
#include <bits/stdc++.h>
using namespace std;
 
// Count number of pairs of lines
// having integer intersection point
int countPairs(int* P, int* Q, int N, int M)
{
    // Initialize arrays to store counts
    int A[2] = { 0 }, B[2] = { 0 };
 
    // Count number of odd and even Pi
    for (int i = 0; i < N; i++)
        A[P[i] % 2]++;
 
    // Count number of odd and even Qi
    for (int i = 0; i < M; i++)
        B[Q[i] % 2]++;
 
    // Return the count of pairs
    return (A[0] * B[0] + A[1] * B[1]);
}
 
// Driver code
int main()
{
    int P[] = { 1, 3, 2 }, Q[] = { 3, 0 };
    int N = sizeof(P) / sizeof(P[0]);
    int M = sizeof(Q) / sizeof(Q[0]);
 
    cout << countPairs(P, Q, N, M);
 
    return 0;
}

// Java program to Number of pairs of lines
// having integer intersection points
class GFG
{
 
// Count number of pairs of lines
// having integer intersection point
static int countPairs(int []P, int []Q,
                      int N, int M)
{
    // Initialize arrays to store counts
    int []A = new int[2], B = new int[2];
 
    // Count number of odd and even Pi
    for (int i = 0; i < N; i++)
        A[P[i] % 2]++;
 
    // Count number of odd and even Qi
    for (int i = 0; i < M; i++)
        B[Q[i] % 2]++;
 
    // Return the count of pairs
    return (A[0] * B[0] + A[1] * B[1]);
}
 
// Driver code
public static void main(String[] args)
{
    int []P = { 1, 3, 2 };
    int []Q = { 3, 0 };
    int N = P.length;
    int M = Q.length;
 
    System.out.print(countPairs(P, Q, N, M));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to Number of pairs of lines
# having eger ersection pos
 
# Count number of pairs of lines
# having eger ersection po
def countPairs(P, Q, N, M):
     
    # Initialize arrays to store counts
    A = [0] * 2
    B = [0] * 2
 
    # Count number of odd and even Pi
    for i in range(N):
        A[P[i] % 2] += 1
 
    # Count number of odd and even Qi
    for i in range(M):
        B[Q[i] % 2] += 1
 
    # Return the count of pairs
    return (A[0] * B[0] + A[1] * B[1])
 
# Driver code
 
P = [1, 3, 2]
Q = [3, 0]
N = len(P)
M = len(Q)
 
print(countPairs(P, Q, N, M))
 
# This code is contributed by mohit kumar 29

// C# program to Number of pairs of lines
// having integer intersection points
using System;
 
class GFG
{
     
    // Count number of pairs of lines
    // having integer intersection point
    static int countPairs(int []P, int []Q,
                        int N, int M)
    {
        // Initialize arrays to store counts
        int []A = new int[2];
        int []B = new int[2];
     
        // Count number of odd and even Pi
        for (int i = 0; i < N; i++)
            A[P[i] % 2]++;
     
        // Count number of odd and even Qi
        for (int i = 0; i < M; i++)
            B[Q[i] % 2]++;
     
        // Return the count of pairs
        return (A[0] * B[0] + A[1] * B[1]);
    }
     
    // Driver code
    public static void Main()
    {
        int []P = { 1, 3, 2 };
        int []Q = { 3, 0 };
        int N = P.Length;
        int M = Q.Length;
     
        Console.Write(countPairs(P, Q, N, M));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Javascript program to Number of
// pairs of lines having integer
// intersection points
 
// Count number of pairs of lines
// having integer intersection point
function countPairs(P, Q, N, M)
{
     
    // Initialize arrays to store counts
    var A = [0, 0], B = [0, 0];
 
    // Count number of odd and even Pi
    for(var i = 0; i < N; i++)
        A[P[i] % 2]++;
 
    // Count number of odd and even Qi
    for(var i = 0; i < M; i++)
        B[Q[i] % 2]++;
 
    // Return the count of pairs
    return(A[0] * B[0] + A[1] * B[1]);
}
 
// Driver code
var P = [ 1, 3, 2 ], Q = [ 3, 0 ];
var N = P.length;
var M = Q.length;
 
document.write(countPairs(P, Q, N, M));
 
// This code is contributed by rrrtnx
 
</script>

3

Complejidad del Tiempo: O(P + Q)

Espacio Auxiliar: O(1)