小羊杯 J

冷酷的数

https://ac.nowcoder.com/acm/contest/100672/J

用欧拉筛筛出 2e5 范围内的所有质数,再遍历质数数组判断是否满足题目要求即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int pr[N],minp[N],vis[N];
int cnt=0;
void ol(int x)
{
    for(int i=2;i<=x;i++)
    {
        if(!vis[i])
        {
            pr[cnt++]=i;
            minp[i]=i;
        }
        for(int j=0;j<cnt;j++)
        {
            if(pr[j]*i>x) break;
            vis[pr[j]*i]=1;
            minp[pr[j]*i]=pr[j];
            if(i%pr[j]==0) break;
        }
    }
}
int main(){
    int t; cin>>t;
    ol(N-10);
    while(t--){
        int x,y; cin>>x>>y;
        int l=min(x,y),r=max(x,y);
        int ans=-1;
        
        for(int i=0;i<=cnt;i++){
            int xx=gcd(x,pr[i]),yy=gcd(y,pr[i]);
            if(pr[i]>r) break;
            if(xx==1&&yy==1){
                ans=pr[i];
                break;
            }
        }
        cout<<ans<<endl;
    }
}
全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
04-08 10:36
已编辑
华南理工大学 C++
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务