Calcular a soma dos valores entre um intervalo.

[Gabriel Schumacher]

O exercício pede que eu calcule a soma dos valores entre um intervalo, incluindo os valores. Exemplo [1,5]=15 (1+2+3+4+5). O exercício é do site URI, só que estou recebendo "time limit exceeded", ou seja, está muito lento. Como posso melhorá-lo? Lembrando que os valores de entrada pode ir até 10^9, como fiz um laço de repetição de 1 por 1 acho q esse é o motivo de estar lento. Link do exercício: https://www.urionlinejudge.com.br/repository/UOJ_1805.html

 

//1805.c

#include <stdio.h>

int main(int argc, char **argv)
{
	long a,b,s=0,i,ma,me;

	scanf("%ld %ld",&a,&b);

	if(a>b){
		ma=a;
		me=b;
	}else{
		ma=b;
		me=a;
	}

	for(i=me;i<=ma;i++){
		s+=i;
	}
	printf("%ld\n",s);


	return 0;
}

 

[Carlos Zanon]

@Gabriel Schumacher Você pode calcular ele usando progressão aritmética (PA)

 

#include <stdio.h>
#include <stdlib.h>

int calcularDistancia(long, long, int);
long calcularSomatorio(long, long, int);

int main()
{
	// a1 = posição inicial da PA.
	// an = posição final da PA.
	// sn = Somatório de todos os elementos desde a1 até an
	long a1, an, sn;
	// esta PA é de razão 1
	int r = 1;
	
	// Obtém os valores para a1 e an
	scanf("%ld %ld", &a1, &an);

	// Se a1 for maior que an,
	// então troca os valores. É possível também negativar a razão.
	if(a1 > an)
	{
		long aux = a1;
		a1 = an;
		an = aux;
	}

	// Calcula o somatório dos itens da PA
	sn = calcularSomatorio(a1, an, r);

	// Exibe em tela o somatório.
	printf("%ld\n", sn);
	
	return 0;
}

/**
 * Calcula o somatório de a1 até an
 *
 * @param a1 Posição incial
 * @param an Posição final
 * @param r Razão da PA
 *
 * @return Valor do somatório do PA.
 */
long calcularSomatorio(long a1, long an, int r)
{
	int n = calcularDistancia(a1, an, r);

	return ((a1 + an) * n)/2;
}

/**
 * Obtém qual é a posição de an dentro da PA
 * 
 * @param a1 Posição inicial da PA
 * @param an Posição final da PA
 * @param r Razão razão da PA
 *
 * @return int Posição de an dentro da PA.
 */
int calcularDistancia(long a1, long an, int r)
{
	return ((an - a1)/r) + 1;
}

 

[Gabriel Schumacher]

1 hora atrás, Carlos Zanon disse:

@Gabriel Schumacher Você pode calcular ele usando progressão aritmética (PA)

 

#include <stdio.h>
#include <stdlib.h>

int calcularDistancia(long, long, int);
long calcularSomatorio(long, long, int);

int main()
{
	// a1 = posição inicial da PA.
	// an = posição final da PA.
	// sn = Somatório de todos os elementos desde a1 até an
	long a1, an, sn;
	// esta PA é de razão 1
	int r = 1;
	
	// Obtém os valores para a1 e an
	scanf("%ld %ld", &a1, &an);

	// Se a1 for maior que an,
	// então troca os valores. É possível também negativar a razão.
	if(a1 > an)
	{
		long aux = a1;
		a1 = an;
		an = aux;
	}

	// Calcula o somatório dos itens da PA
	sn = calcularSomatorio(a1, an, r);

	// Exibe em tela o somatório.
	printf("%ld\n", sn);
	
	return 0;
}

/**
 * Calcula o somatório de a1 até an
 *
 * @param a1 Posição incial
 * @param an Posição final
 * @param r Razão da PA
 *
 * @return Valor do somatório do PA.
 */
long calcularSomatorio(long a1, long an, int r)
{
	int n = calcularDistancia(a1, an, r);

	return ((a1 + an) * n)/2;
}

/**
 * Obtém qual é a posição de an dentro da PA
 * 
 * @param a1 Posição inicial da PA
 * @param an Posição final da PA
 * @param r Razão razão da PA
 *
 * @return int Posição de an dentro da PA.
 */
int calcularDistancia(long a1, long an, int r)
{
	return ((an - a1)/r) + 1;
}

 

Nossa, nem lembravam mais dessa fórmula. valeu