Advertisement
Guest User

Untitled

a guest
May 23rd, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.14 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAXN 110
  5.  
  6. long long gcd(long long a, long long b)
  7. {
  8.     long long int r;
  9.  
  10.     while (b != 0)
  11.     {
  12.         r = a % b;
  13.         a = b;
  14.         b = r;
  15.     }
  16.  
  17.     return a;
  18. }
  19. long long mmc(long long num1, long long num2) {
  20.  
  21.     long long resto, a, b;
  22.  
  23.     a = num1;
  24.     b = num2;
  25.  
  26.     do {
  27.         resto = a % b;
  28.  
  29.         a = b;
  30.         b = resto;
  31.  
  32.     } while (resto != 0);
  33.  
  34.     return ( num1 * num2) / a;
  35. }
  36.  
  37. int main(void){
  38.         //freopen("output_lari.txt", "w", stdout);
  39.         long long i,N,T,bola,variavel=0;
  40.         do{
  41.         variavel=0;
  42.         scanf("%lld",&N);
  43.         scanf("%lld",&T);
  44.         if(N>=1 && N<=100 && T>=1 && T<= 100000){
  45.                 long long array[MAXN] = {0}, encontrado[100010] = {0};
  46.                 for(i=0;i<N;i++){
  47.                         scanf("%lld",&bola);
  48.                         if(bola>=1 && bola<= T){
  49.                                 array[i]=bola;
  50.                                 encontrado[array[i]] = 1;
  51.                         }else{
  52.                                 return 1;
  53.                         }
  54.                         if(T%array[i]!=0){
  55.                                 variavel++;
  56.                         }
  57.  
  58.                 }
  59.  
  60.                 if(variavel!=0){
  61.                         printf("impossivel\n");
  62.                         continue; // OBS: vc esqueceu disso daqui, do contrario vai ser impossivel e ele vai executar o codigo abaixo ao inves de ir
  63.                         // para o proximo teste...
  64.                 }
  65.                 int var=0;
  66.  
  67.                 // OBS: so precisamos calcular mmc entre todos os numeros 1 vez, afinal a array nao muda mais
  68.                 long long p,j, mmc_inicial= array[0];
  69.                 for(p=1;p<N;p++){// calcula mmc entre os nums do array
  70.                                 mmc_inicial= mmc(mmc_inicial, array[p]);
  71.                         }
  72.  
  73.                 // queremos achar um numero k tq mmc(mmc_inicial, k) == t seja vdd pela 1a vez..
  74.                 long long k;
  75.                 for(k=2; k<=T;k++){
  76.                         long long mmc_final = mmc(mmc_inicial, k);
  77.                         if ( mmc_final == T && encontrado[k] != 1)
  78.                         {
  79.                             break;
  80.                         }
  81.  
  82.                         //if(T%k==0){//testa se cada um dos valores entre 2-T é divisivel por T
  83.  
  84.                                 /* OBS:
  85.                                 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
  86.                                 int p,j;
  87.                                 for(p=1;p<N;p++){// calcula mmc entre os nums do array
  88.                                                 mmc_inicial= mmc(mmc_inicial, array[p]);
  89.                                         }
  90.                                         int mmc_final= mmc(mmc_inicial,i);//insere o i no mmc
  91.                                 */
  92.  
  93.                                 /* IMPORTANTE AQUI:
  94.                                 N entendi o que esse bloco faz :( Se puder explicar talvez eu entenda melhor...
  95.                                 for(j=0;j<N;j++){// testa se esse valor divisivel por T ja nao esta no array
  96.                                         if(array[j]==i){
  97.                                                 var=0;
  98.                                                 break;
  99.                                         }
  100.                                         if (array[j]!=i && mmc_final==T){
  101.                                                 var=i;
  102.                                         }
  103.                                 }*/
  104.                         //}
  105.  
  106.                 /*if (var!=0 && variavel==0){
  107.                         printf("%d\n", var);
  108.                         break;*/
  109.                 }
  110.  
  111.                 if (k <= T)
  112.                 {
  113.                     printf("%lld\n", k);
  114.                 }
  115.                 else
  116.                 {
  117.                     printf("impossivel\n");
  118.                 }
  119.             }
  120.         } while(N!=0 && T!=0);
  121.  
  122.                 return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement