daily pastebin goal
25%
SHARE
TWEET

Untitled

a guest Oct 20th, 2018 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //3413 - Reduced ID Numbers
  2. //Live Archive
  3.  
  4. /*
  5. Queremos achar o menor k para que todo a,b da entrada não aconteça que a%k = b%k
  6. a%k = b%k
  7. a%k - b%k = 0
  8. (a-b)%k = 0
  9.  
  10. Seja x = abs(a-b)
  11.  
  12. Para todo a,b teste todos os possíveis valores de k de 1 até sqrt(x)
  13. Se sqrt(x)%k = 0 então k e sqrt(x)/k não são valores válidos.
  14. Marque todos os valores não validos, depois procure o primeiro valor não marcado.
  15. */
  16.  
  17. #include <cstdio>
  18. #include <cstdlib>
  19. #include <string>
  20. #include <cmath>
  21. #include <cstring>
  22. #include <algorithm>
  23. #include <utility>
  24. #include <queue>
  25. #include <stack>
  26. #include <vector>
  27. #include <map>
  28. #include <iostream>
  29.  
  30. #define ln printf("\n")
  31.  
  32. using namespace std;
  33.  
  34. int n;
  35. int r[330];
  36. bool mark[1000010];
  37.  
  38. bool read(){   
  39.     scanf("%d", &n);
  40.    
  41.     for(int i = 0; i < n; i++){
  42.         scanf("%d", &r[i]);
  43.     }
  44.    
  45.     return true;
  46. }
  47.  
  48. void combine(int x){
  49.     for(int i = 1; i*i <= x; i++){
  50.         if(!(x%i)){
  51.             mark[i] = true;
  52.             mark[x/i] = true;
  53.         }
  54.     }  
  55. }
  56.  
  57. void process(){
  58.     memset(mark, false, sizeof(mark));
  59.    
  60.     for(int i = 0; i < n; i++){
  61.         for(int j = i+1; j < n; j++){
  62.             combine(abs(r[i] - r[j]));
  63.         }
  64.     }
  65.    
  66.     int res = 1;
  67.    
  68.     while(mark[res]) res++;
  69.    
  70.     printf("%d\n", res);
  71.    
  72. }
  73.  
  74. int main(){
  75.     //freopen("in", "r", stdin);   
  76.     int cases; scanf("%d", &cases);
  77.    
  78.  
  79.    
  80.     while(cases-- && /**/ read()){     
  81.         process();
  82.     }
  83.    
  84.     //while(1);
  85.    
  86.     return 0;
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top