Atcoder Beginner Contest 254 F - Rectangle GCD 解題心得( 題目 )
解題概念:數學、線段樹
解題方法:本題如果直接做一定是超時，用二維的線段樹恐怕也塞不下(空間也會炸)，所以要想想別的方法，GCD有個著名的求法是輾轉相除，因為同一列、行，如果做輾轉相除，其實可以發現好像會互相抵消，利用這個性質，可以先記得A、B陣列的差分，建兩顆線段樹，答案就是區間內GCD與其中真正一項(L1,L2)做GCD，時間複雜度為O(NlogN)。
//Author:En Chi Tsung(欉恩祁)
//Date:2022/06/08
import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static long ret;
public static int reti,rd;
public static boolean neg;
public static final int mod=998244353;
public static final int MAX=200005;
public static int[] A=new int[MAX];
public static int[] dA=new int[MAX];
public static int[] sA=new int[MAX<<2];
public static int[] B=new int[MAX];
public static int[] dB=new int[MAX];
public static int[] sB=new int[MAX<<2];
public static Useful us=new Useful(mod);
public static void main(String[] args) throws Exception{
final int n=readint();
final int q=readint();
for(int i=1;i<=n;i++) {
A[i]=readint();
}
for(int i=1;i<=n;i++) {
B[i]=readint();
}
for(int i=1;i<n;i++) {
dA[i]=Math.abs(A[i+1]-A[i]);
dB[i]=Math.abs(B[i+1]-B[i]);
}
if(n!=1)build(1,n-1,1,sA,dA);
if(n!=1)build(1,n-1,1,sB,dB);
int l1,r1,l2,r2,a1,a2,ans;
for(int i=0;i<q;i++) {
l1=readint();
r1=readint();
l2=readint();
r2=readint();
a1=a2=0;
if(l1!=r1)a1=query(1,n-1,l1,r1-1,1,sA);
if(l2!=r2)a2=query(1,n-1,l2,r2-1,1,sB);
ans=us.gcd(A[l1]+B[l2],us.gcd(a1,a2));
bw.write(ans+"\n");
}
bw.flush();
}
public static int build(int l,int r,int now,int[] seg,int[] A) {
if(l==r) {
seg[now]=A[l];
return A[l];
}
int mid=(l+r)>>1;
seg[now]=us.gcd(build(l,mid,now<<1,seg,A),build(mid+1,r,(now<<1)|1,seg,A));
return seg[now];
}
public static int query(int l,int r,int ql,int qr,int now,int[] seg) {
if(l>qr||r<ql) {
return 0;
}
if(qr>=r&&l>=ql) {
return seg[now];
}
int mid=(l+r)>>1;
return us.gcd(query(l,mid,ql,qr,now<<1,seg),query(mid+1,r,ql,qr,(now<<1)|1,seg));
}
public static int readint() throws Exception{
reti=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
reti*=10;
reti+=(rd&15);
rd=br.read();
}
if(neg)reti*=-1;
return reti;
}
public static long readlong() throws Exception{
ret=0;
neg=false;
while(rd<48||rd>57) {
rd=br.read();
if(rd=='-') {
neg=true;
}
}
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
/*
*/
/*
*/
class Pii{
int x,y;
Pii(int a,int b){
x=a;
y=b;
}
}
class Pll{
long x,y;
Pll(long a,long b){
x=a;
y=b;
}
}
class Useful{
long mod;
Useful(long m){mod=m;}
void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
long fast(long x,long pw) {
if(pw==1)return x;
long h=fast(x,pw>>1);
if((pw&1)==0) {
return h*h%mod;
}
return h*h%mod*x%mod;
}
int gcd(int a,int b) {
if(a==0)return b;
if(b==0)return a;
return gcd(b,a%b);
}
long gcd(long a,long b) {
if(a==0)return b;
if(b==0)return a;
return gcd(b,a%b);
}
long lcm(long a, long b){
return a*(b/gcd(a,b));
}
double log2(int x) {
return (Math.log(x)/Math.log(2));
}
double log2(long x) {
return (Math.log(x)/Math.log(2));
}
}
文章標籤
全站熱搜
留言列表
