fork download 
  1. #include <bits/stdc++.h>
  2. #define lb lower_bound
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define op freopen
  9. #define sz size
  10. #define TXT "test"
  11. #define freo if(fopen(TXT".inp","r")){op(TXT".inp","r",stdin);op(TXT".out","w",stdout);}
  12. using namespace std;
  13.  
  14. int n,a[100005],b[100005],q,st[100005][20];
  15.  
  16. void setup()
  17. {
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         st[i][0]=a[i];
  21.     }
  22.     for(int j=1;(1<<j)<=n;j++)
  23.     {
  24.         for(int i=0;i+(1<<j)-1<=n;i++)
  25.         {
  26.             st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
  27.         }
  28.     }
  29. }
  30. int get(int l,int r)
  31. {
  32.     int j=31 - __builtin_clz(r-l+1);
  33.     return __gcd(st[l][j],st[r-(1<<(j-1))][j]);
  34. }
  35. main()
  36. {
  37.     ios;
  38.     freo;
  39.     cin>>n>>q;
  40.     for(int i=1;i<=n;i++)
  41.     {
  42.         cin>>a[i];
  43.     }
  44.     for(int i=1;i<=n;i-=-1)
  45.     {
  46.         cin>>b[i];
  47.         a[i]=abs(a[i]-b[i]);
  48.     }
  49.     setup();
  50.     while(q--)
  51.     {
  52.         int l,r;
  53.         cin>>l>>r;
  54.         cout<<get(l,r)<<"\n";
  55.     }
  56. }
Success #stdin #stdout 0.01s 5640KB
comments (?)
stdin 
3 3
1 3 10
10 15 2
1 2
2 3
1 3
stdout 
3
4
1
https://ideone.com/pkUQ7E
language:
C++ (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!