Contar progresiones aritméticas que tienen suma S y diferencia común igual a D

Dados dos enteros S y D , la tarea es contar el número de progresiones aritméticas posibles con suma S y diferencia común D .

Ejemplos:

Entrada: S = 12, D = 1
Salida: 4
Explicación: Son posibles las siguientes 4 progresiones aritméticas con suma 12 y diferencia común 1:

1. {1, 2}
2. {3, 4, 5}
3. {-2, -1, 0, 1, 2, 3, 4, 5}
4. {-11, -10, -9, …, 10, 11, 12}

Entrada: S = 1, D = 1
Salida: 2

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• La suma de la serie AP está dada por:

donde, 
S es la suma de la serie AP, 
a es el primer término de la serie, 
N es el número de términos de la serie, 
d es una diferencia común

• Después de reorganizar las expresiones anteriores:

=> 2*S = N*(2*a + (N – 1)*d) … (1)

=>    …(2)

• De las dos expresiones anteriores:
  • La idea es considerar todos los factores de 2*S y comprobar si existe algún factor F tal que el producto de F y (2*a + (F – 1)*d) sea igual a 2 * S . Si se encuentra que es cierto, entonces cuente ese factor para uno de los posibles AP que tienen la suma S dada .
  • Si existe algún factor F , tal que (D * F – (2 * S / F) + D) es divisible por 2 , entonces cuente ese factor para uno de los posibles AP que tienen la suma dada S .

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos answer , para almacenar el conteo de AP s con suma S y diferencia común D .
• Itere sobre el rango [1, √2*S] y verifique si 2 * S es divisible por i , luego realice los siguientes pasos:
  • Si el valor de ((2 * S / i) + 1 – i * D) es divisible por 2 , entonces incremente la respuesta en 1 .
  • Si el valor de (i * D – S / i + 1) es divisible por 2 , entonces incrementa la respuesta en 1 .
• Después de completar los pasos anteriores, imprima el valor de la respuesta como el conteo resultante de AP s.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of APs
// with sum S and common difference D
int countAPs(int S, int D)
{
    // Multiply S by 2
    S = S * 2;
 
    // Stores the count of APs
    int answer = 0;
 
    // Iterate over the factors of 2*S
    for (int i = 1; i <= sqrt(S); i++) {
 
        // Check if i is the factor
        // or not
        if (S % i == 0) {
 
            // Conditions to check if AP
            // can be formed using factor F
            if (((S / i) - D * i + D) % 2 == 0)
                answer++;
 
            if ((D * i - (S / i) + D) % 2 == 0)
                answer++;
        }
    }
 
    // Return the total count of APs
    return answer;
}
 
// Driver Code
int main()
{
    int S = 12, D = 1;
    cout << countAPs(S, D);
 
    return 0;
}

// Java program for above approach
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
   
// Function to count the number of APs
// with sum S and common difference D
static int countAPs(int S, int D)
{
   
    // Multiply S by 2
    S = S * 2;
 
    // Stores the count of APs
    int answer = 0;
 
    // Iterate over the factors of 2*S
    for (int i = 1; i <= Math.sqrt(S); i++) {
 
        // Check if i is the factor
        // or not
        if (S % i == 0) {
 
            // Conditions to check if AP
            // can be formed using factor F
            if (((S / i) - D * i + D) % 2 == 0)
                answer++;
 
            if ((D * i - (S / i) + D) % 2 == 0)
                answer++;
        }
    }
 
    // Return the total count of APs
    return answer;
}
 
// Driver code
public static void main(String[] args)
{
    int S = 12, D = 1;
    System.out.println(countAPs(S, D));
}
}
 
// This code is contributed by susmitakundugoaldanga.

# Python3 program for the above approach
 
# Function to count the number of APs
# with sum S and common difference D
def countAPs(S, D):
   
    # Multiply S by 2
    S = S * 2
 
    # Stores the count of APs
    answer = 0
 
    # Iterate over the factors of 2*S
    for i in range(1, S):
 
        if i * i > S:
            break
             
        # Check if i is the factor
        # or not
        if (S % i == 0):
 
            # Conditions to check if AP
            # can be formed using factor F
            if (((S // i) - D * i + D) % 2 == 0):
                answer += 1
 
            if ((D * i - (S // i) + D) % 2 == 0):
                answer += 1
 
    # Return the total count of APs
    return answer
 
# Driver Code
if __name__ == '__main__':
    S, D = 12, 1
    print(countAPs(S, D));
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
class GFG{
 
  // Function to count the number of APs
  // with sum S and common difference D
  static int countAPs(int S, int D)
  {
 
    // Multiply S by 2
    S = S * 2;
 
    // Stores the count of APs
    int answer = 0;
 
    // Iterate over the factors of 2*S
    for (int i = 1; i <= Math.Sqrt(S); i++) {
 
      // Check if i is the factor
      // or not
      if (S % i == 0) {
 
        // Conditions to check if AP
        // can be formed using factor F
        if (((S / i) - D * i + D) % 2 == 0)
          answer++;
 
        if ((D * i - (S / i) + D) % 2 == 0)
          answer++;
      }
    }
 
    // Return the total count of APs
    return answer;
  }
 
 
  // Driver code
  static void Main()
  {
    int S = 12, D = 1;
    Console.Write(countAPs(S, D));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
 
// Javascript program for the above approach
 
// Function to count the number of APs
// with sum S and common difference D
function countAPs(S, D)
{
   
    // Multiply S by 2
    S = S * 2;
 
    // Stores the count of APs
    let answer = 0;
 
    // Iterate over the factors of 2*S
    for (let i = 1; i <= Math.sqrt(S); i++) {
 
        // Check if i is the factor
        // or not
        if (S % i == 0) {
 
            // Conditions to check if AP
            // can be formed using factor F
            if (((S / i) - D * i + D) % 2 == 0)
                answer++;
 
            if ((D * i - (S / i) + D) % 2 == 0)
                answer++;
        }
    }
 
    // Return the total count of APs
    return answer;
}
 
// Driver code
     
    let S = 12, D = 1;
    document.write(countAPs(S, D));
     
</script>

4

Complejidad Temporal: O(√S) 
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.