Dado un número entero N , la tarea es contar toda la progresión aritmética con
Ejemplos:
Entrada: N = 12
Salida: 3
Explicación:
Los siguientes tres AP cumplen las condiciones requeridas:
- {3, 4, 5}
- {−2, −1, 0, 1, 2, 3, 4, 5}
- {−11, −10, −9, …, 10, 11, 12]}
Entrada: N = 963761198400
Salida: 1919
Enfoque: El problema dado se puede resolver utilizando las siguientes propiedades de AP:
S = norte / 2 [2 *A + norte – 1].
Reordenando esto y multiplicando ambos lados por 2
=> 2 * S = N * (N + 2 * A − 1)Reorganizando aún más
=> A = ((2 * N / i ) − i + 1) / 2.Ahora, itera sobre todos los factores de 2 * N y verifica para cada factor i si (2 * N/i) − i + 1 es par o no.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar, para almacenar el número de series AP posibles habiendo dado las condiciones.
- Iterar a través de todos los factores de 2 * N y para cada i -ésimo factor, verificar si (2 * N / i) − i + 1 es par.
- Si se encuentra que es cierto, incremente el conteo.
- Imprima el conteo: 1 como la respuesta requerida, ya que la secuencia que consta solo de N debe descartarse.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count all possible
// AP series with common difference
// 1 and sum of elements equal to N
void countAPs(long long int N)
{
// Stores the count of AP series
long long int count = 0;
// Traverse through all factors of 2 * N
for (long long int i = 1;
i * i <= 2 * N; i++) {
long long int res = 2 * N;
if (res % i == 0) {
// Check for the given conditions
long long int op = res / i - i + 1;
if (op % 2 == 0) {
// Increment count
count++;
}
if (i * i != res
and (i - res / i + 1) % 2 == 0) {
count++;
}
}
}
// Print count - 1
cout << count - 1 << "\n";
}
// Driver Code
int main()
{
// Given value of N
long long int N = 963761198400;
// Function call to count
// required number of AP series
countAPs(N);
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to count all possible
// AP series with common difference
// 1 and sum of elements equal to N
static void countAPs(long N)
{
// Stores the count of AP series
long count = 0;
// Traverse through all factors of 2 * N
for (long i = 1; i * i <= 2 * N; i++) {
long res = 2 * N;
if (res % i == 0) {
// Check for the given conditions
long op = res / i - i + 1;
if (op % 2 == 0) {
// Increment count
count++;
}
if (i * i != res
&& (i - res / i + 1) % 2 == 0) {
count++;
}
}
}
// Print count - 1
System.out.println(count - 1);
}
// Driver code
public static void main(String[] args)
{
// Given value of N
long N = 963761198400L;
// Function call to count
// required number of AP series
countAPs(N);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program to implement # the above approach # Function to count all possible # AP series with common difference # 1 and sum of elements equal to N def countAPs(N) : # Stores the count of AP series count = 0 # Traverse through all factors of 2 * N i = 1 while(i * i <= 2 * N) : res = 2 * N if (res % i == 0) : # Check for the given conditions op = res / i - i + 1 if (op % 2 == 0) : # Increment count count += 1 if (i * i != res and (i - res / i + 1) % 2 == 0) : count += 1 i += 1 # Print count - 1 print(count - 1) # Driver Code # Given value of N N = 963761198400 # Function call to count # required number of AP series countAPs(N) # This code is contributed by sanjoy_62.
C#
// C# program for above approach
using System;
public class GFG
{
// Function to count all possible
// AP series with common difference
// 1 and sum of elements equal to N
static void countAPs(long N)
{
// Stores the count of AP series
long count = 0;
// Traverse through all factors of 2 * N
for (long i = 1; i * i <= 2 * N; i++) {
long res = 2 * N;
if (res % i == 0) {
// Check for the given conditions
long op = res / i - i + 1;
if (op % 2 == 0) {
// Increment count
count++;
}
if (i * i != res
&& (i - res / i + 1) % 2 == 0) {
count++;
}
}
}
// Print count - 1
Console.WriteLine(count - 1);
}
// Driver code
public static void Main(String[] args)
{
// Given value of N
long N = 963761198400L;
// Function call to count
// required number of AP series
countAPs(N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to count all possible
// AP series with common difference
// 1 and sum of elements equal to N
function countAPs(N)
{
// Stores the count of AP series
let count = 0;
// Traverse through all factors of 2 * N
for (let i = 1; i * i <= 2 * N; i++) {
let res = 2 * N;
if (res % i == 0) {
// Check for the given conditions
let op = res / i - i + 1;
if (op % 2 == 0) {
// Increment count
count++;
}
if (i * i != res
&& (i - res / i + 1) % 2 == 0) {
count++;
}
}
}
// Print count - 1
document.write(count - 1);
}
// Driver code
// Given value of N
let N = 963761198400;
// Function call to count
// required number of AP series
countAPs(N);
</script>
Producción:
1919
Complejidad de Tiempo: O(√N) Espacio
Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA