daily pastebin goal
30%
SHARE
TWEET

Untitled

a guest Feb 12th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int *logs(int m) //log_table
  6. {
  7.     int cap = pow(2, m);
  8.     int *lg = (int *) calloc (cap, sizeof(int));
  9.    
  10.     int i = 1, j = 0;
  11.    
  12.     while (i < m)
  13.     {
  14.         while (j < cap)
  15.         {
  16.             lg[j] = i - 1;
  17.             j++;
  18.         }
  19.        
  20.         i++;
  21.     }
  22.    
  23.     return lg;
  24. }
  25.  
  26. int *st_build(int *p, int n, int *lg) //sparse_table create
  27. {
  28.     int m = lg[n] + 1;
  29.    
  30.     int st[n][m];
  31.    
  32.     int i = 0;
  33.    
  34.     while (i < n)
  35.     {
  36.         st[i][0] = p[i];
  37.         i++;
  38.     }
  39.    
  40.     int j = 1;
  41.    
  42.     while (j < m)
  43.     {
  44.         i = 0;
  45.        
  46.         while (i <= n - pow(2, j))
  47.         {
  48.             st[i][j] = gcd(st[i][pow(2, j)], st[i + pow(2, j - 1)][j - 1]);
  49.             i++;
  50.         }
  51.        
  52.         j++;
  53.     }
  54.    
  55.     return st;
  56. }
  57.  
  58. int gcd(int a, int b) //gcd
  59. {
  60.     if (a < 0 || b < 0) return (a < 0) ? b : a;
  61.  
  62.     if (a == 0 || b == 0) return (a == 0) ? b : a;
  63.  
  64.     if (a < b)
  65.         {
  66.         int t = a;
  67.         a = b;
  68.         b = t;
  69.     }
  70.  
  71.     while(b > 0)
  72.     {
  73.         int t = a % b;
  74.         a = b;
  75.         b = t;
  76.     }
  77.  
  78.     return a;
  79. }
  80.  
  81. st_query(int *st, int l, int r, int *logs) //sparse_table query
  82. {
  83.     int j = logs[r - l + 1];
  84.     int v = gcd(st[l][j], st[r - pow(2, j) + 1][j]);
  85. }
  86.  
  87. int main(int argc, char **argv)
  88. {
  89.     int N = 0;
  90.     scanf("%lu", &N);
  91.  
  92.     int *array = (int *) malloc(N * sizeof(int));
  93.     int *lg = logs(N);
  94.  
  95.     for (int i = 0; i < N; i++)
  96.         scanf("%d ", &array[i]);
  97.  
  98.     int K;
  99.     scanf("%d\n", &K);
  100.  
  101.     for (int i = 0; i < K; i++)
  102.     {
  103.         int l, r;
  104.  
  105.         scanf("%d %d", &l, &r);
  106.    
  107.         int *st = st_build(array, N, lg);
  108.        
  109.         printf("%d\n", st_query(st, l, r, lg));
  110.     }
  111.  
  112.     free(lg);
  113.     free(array);
  114.    
  115.     return 0;
  116. }
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