Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define MAXN 110
- long long gcd(long long a, long long b)
- {
- long long int r;
- while (b != 0)
- {
- r = a % b;
- a = b;
- b = r;
- }
- return a;
- }
- long long mmc(long long num1, long long num2) {
- long long resto, a, b;
- a = num1;
- b = num2;
- do {
- resto = a % b;
- a = b;
- b = resto;
- } while (resto != 0);
- return ( num1 * num2) / a;
- }
- int main(void){
- //freopen("output_lari.txt", "w", stdout);
- long long i,N,T,bola,variavel=0;
- do{
- variavel=0;
- scanf("%lld",&N);
- scanf("%lld",&T);
- if(N>=1 && N<=100 && T>=1 && T<= 100000){
- long long array[MAXN] = {0}, encontrado[100010] = {0};
- for(i=0;i<N;i++){
- scanf("%lld",&bola);
- if(bola>=1 && bola<= T){
- array[i]=bola;
- encontrado[array[i]] = 1;
- }else{
- return 1;
- }
- if(T%array[i]!=0){
- variavel++;
- }
- }
- if(variavel!=0){
- printf("impossivel\n");
- continue; // OBS: vc esqueceu disso daqui, do contrario vai ser impossivel e ele vai executar o codigo abaixo ao inves de ir
- // para o proximo teste...
- }
- int var=0;
- // OBS: so precisamos calcular mmc entre todos os numeros 1 vez, afinal a array nao muda mais
- long long p,j, mmc_inicial= array[0];
- for(p=1;p<N;p++){// calcula mmc entre os nums do array
- mmc_inicial= mmc(mmc_inicial, array[p]);
- }
- // queremos achar um numero k tq mmc(mmc_inicial, k) == t seja vdd pela 1a vez..
- long long k;
- for(k=2; k<=T;k++){
- long long mmc_final = mmc(mmc_inicial, k);
- if ( mmc_final == T && encontrado[k] != 1)
- {
- break;
- }
- //if(T%k==0){//testa se cada um dos valores entre 2-T é divisivel por T
- /* OBS:
- aqui vc calcula o mmc entre todos os numeros varias vezes, mas a array nao muda! pode dar TLE dependendo da entrada, melhor n arriscar
- int p,j;
- for(p=1;p<N;p++){// calcula mmc entre os nums do array
- mmc_inicial= mmc(mmc_inicial, array[p]);
- }
- int mmc_final= mmc(mmc_inicial,i);//insere o i no mmc
- */
- /* IMPORTANTE AQUI:
- N entendi o que esse bloco faz :( Se puder explicar talvez eu entenda melhor...
- for(j=0;j<N;j++){// testa se esse valor divisivel por T ja nao esta no array
- if(array[j]==i){
- var=0;
- break;
- }
- if (array[j]!=i && mmc_final==T){
- var=i;
- }
- }*/
- //}
- /*if (var!=0 && variavel==0){
- printf("%d\n", var);
- break;*/
- }
- if (k <= T)
- {
- printf("%lld\n", k);
- }
- else
- {
- printf("impossivel\n");
- }
- }
- } while(N!=0 && T!=0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement