CF #505 B Weakened Common Divisor（数论）题解

题意：给你n组，每组两个数字，要你给出一个数，要求这个是每一组其中一个数的因数（非1），给出任意满足的一个数，不存在则输出-1。

思路1：刚开始乱七八糟暴力了一下果断超时，然后想到了把每组两个数相乘，然后求每组的GCD，那么这个GCD就是因数的乘积（如果GCD==1就输出-1）。然后打个2e5的素筛表，然后找到GCD的一个素数因数。做到这里好像没问题了，然而，分分钟会被hack，问题出在哪里了？显然啊，打素数表只用2e5的范围，但是因数还包括自己本身啊！所以一旦GCD大于2e5我们就找不到答案了，那么我用一个set来储存遇到的大于2e5的数，如果素筛没找到，那就去set里遍历就行了。

思路2：还是那个问题，大于2e5的素数怎么解决。大佬告诉我一个方法，把第一组数据质因数分解，如果分解到最后发现第一组数据的质因数出现了大于2e5的素数，那么就把他存起来，在后面判断。

混合场很不友好，然而我并没有报名，帮别人掉分（逃

代码1：

#include<stack>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn = 2e5+;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

int pr[maxn],p[maxn],pn;

set<ll> st;

void get(){

    pn = ;

    memset(pr,,sizeof(pr));

    for(int i = ;i < maxn;i++){

        if(!pr[i]){

            p[pn++] = i;

            for(ll j = (ll) i * i;j < maxn;j += i){

                pr[j] = ;

            }

        }

    }

}

ull gcd(ull a,ull b){

    return b == ? a : gcd(b,a % b);

}

int main(){

    int n;

    get();

    st.clear();

    scanf("%d",&n);

    ull u,v;

    scanf("%lld%lld",&u,&v);

    if(u >= maxn) st.insert(u);

    if(v >= maxn) st.insert(v);

    ull GCD = u*v;

    bool flag = true;

    for(int i = ;i <= n;i++){

        scanf("%lld%lld",&u,&v);

        if(u >= maxn) st.insert(u);

        if(v >= maxn) st.insert(v);

        GCD = gcd(GCD,u * v);

        if(GCD == ){

            flag = false;

            break;

        }

    }

    if(flag){

        for(int i = ;i < pn && p[i] * p[i] <= GCD;i++){

            if(GCD % p[i] == ){

                printf("%d\n",p[i]);

                return ;

            }

        }

        for(set<ll>::iterator it = st.begin(); it != st.end();++it){

            ll u = *it;

            if(GCD % u == ){

                printf("%lld\n",*it);

                return ;

            }

        }

        printf("%lld\n",GCD);

    }

    else printf("-1\n");

    return ;

}

代码2：

/*

author ：竹攸

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = 2e5+;

typedef long long ll;

ll p[maxn],num[maxn],k,a[maxn],b[maxn];

void prime(){

    for(int i = ; i < maxn; i++){

        if(!num[i]){

            for(ll j = 1LL*i*i; j < maxn; j+=i){

                num[j] = ;

            }

        }

    }

    k = ;

    for(int i = ; i < maxn;i++){

        if(!num[i])

            p[++k] = i;

    }

}

ll gcd(ll a,ll b){

    return b == ?a:gcd(b, a%b);

}

int main(){

    int n;

    ll x, y, a, b, sa, sb;

    prime();

    while(scanf("%d",&n)!=EOF){

        scanf("%lld%lld",&x,&y);

        num[] = x*y;

        if(n == ){    //n等于1的时候先输出

            printf("%lld\n",x);

            continue;

        }

        for(int i = ; i <= k&& x >= p[i]; i++){   //判断x中是否存在大于2e5的素数

            while(x % p[i] == ){

                x /= p[i];

            }

        }

        if(x == )

            a = 2e9+;

        else

            a = x;

        for(int i = ; i <= k&& y >= p[i]; i++){   //y与x 同理

            while(y % p[i] == ){

                y /= p[i];

            }

        }

        if(y == )

            b = 2e9+;

        else

            b = y;

        sa = sb = ;

        for(int i = ; i <= n; i++){

            scanf("%lld%lld",&x,&y);

            num[i] = x*y;

            if(x % a ==  || y % a == )

                sa++;

            if(y % b == || x % b == )

                sb++;

        }

        if(sa == n){

            printf("%lld\n",a);

            continue;

        }

        else if(sb == n){

            printf("%lld\n",b);

            continue;

        }

        ll Gcd = num[];

        for(int i = ; i <= n; i++)

            Gcd = gcd(num[i],Gcd);

        int ans = ;

        for(int i = ; i <= k;i++){

            if(Gcd % p[i] == ){

                ans = p[i];

                break;

            }

        }

        if(ans ==  && Gcd != )

            printf("%lld\n",Gcd);

        else if(ans ==  && Gcd == )

            printf("-1\n");

        else

            printf("%d\n",ans);

    }

    return ;

}

巴特西

CF #505 B Weakened Common Divisor（数论）题解

最新文章

热门文章