Codeforces 1025 B

​​傳送門​​

題目大意

思路

代碼

bool vis[maxn];//标記非素數,0是素數
int primer[maxn/10];//存素數
int cnt=0;//記錄素數個數，
void find_primer(){
    for(int i=2;i <=maxn;i++){
        if(!vis[i])primer[cnt++]=i;
        for(int j=0;j<cnt&&primer[j]*i<=maxn;j++){
            vis[i*primer[j]]=1;//篩
            if(i%primer[j]==0)break;//關鍵！！！找到i*primer[j]的最小質因子primer[j]，退出
        }
    }    
}

set<ll> s;

void init(ll x,ll y){
    for(int i=0;i<cnt&&primer[i]*primer[i]<=x;i++){
        if(x%primer[i]==0){
            while(x%primer[i]==0){
                x/=primer[i];
            }
            s.insert(primer[i]);
        }
    }
    if(x>1) s.insert(x);
    for(int i=0;i<cnt&&primer[i]*primer[i]<=y;i++){
        if(y%primer[i]==0){
            while(y%primer[i]==0){
                y/=primer[i];
            }
            s.insert(primer[i]);
        }
    }
    if(y>1) s.insert(y);
}
ll x[maxn],y[maxn];
int main(){
    int n;
    cin>>n;
    find_primer();
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        
    }
    
    init(x[1],y[1]);
    int flag=1;
    ll ans;
    set<ll>::iterator it; //定義前向疊代器  
    //中序周遊集合中的所有元素  
    for(it=s.begin();it!=s.end();it++){
        int flag1=1;
        for(int j=1;j<=n;j++){
            if(x[j]%(*it)!=0&&y[j]%(*it)!=0){
                flag1=0;
                break;
            }
        }
        if(flag1==1){
            flag=0;
            ans=(*it);
        }
    }
    if(flag==1){
        puts("-1");
    }
    else{
        printf("%lld\n",ans);
    }
}