Gincana - PJF2 - OBI 2016

gincana.cpp

// Medalhas - F2PJ - OBI 2016
// Rogério Júnior
// Complexidade: O(G(i)*log(M))

// obs* G(i) denota max(g(i)), 1<=i<=N,
// onde g(p_n) denota p_n-p_(n-1)
// e p_n denota o n-ésimo primo

#include "iostream"

using namespace std;

// declaro a função MDC
long long mdc(long long a, long long b){
	
	// se a for menor que b, troco seus valores
	if(a<b) swap(a,b);
	
	// agora sei que a>=b
	
	// se b for zero, retorno a
	if(b==0) return a;

	// caso contrário, chamo a recursão para mdc(b,a%b)
	// seguindo o algoritmo de Euclides
	return mdc(b,a%b);
}

int main(){
	
	// declaro as variáveis n, m e resp
	long long n, m, resp;
	
	// leio os valores de n e m
	cin >> n >> m;
	
	// uso um for para percorrer os números que não superam M
	// em orem decrescente
	for(long long i=m;i>=1;i--){
		
		// se o MDC entr o número e N for 1
		if(mdc(i,n)==1){
			
			// então ele é a resposta
			resp=i;
			
			// e posso parar o loop
			break;
		}
	}
	
	// por fim, imprimo o valor da resposta
	cout << resp << "\n";
	
	// e retorno zero
	return 0;
}