Codeforces Round #505 (rated, Div. 1 + Div. 2) B. Weakened Common Divisor

 

题意：定义弱因数x为满足对于一对数{a,b}，{ x | !(x%a) || !(x%b) }

现在问你n对数的公共弱因数

 

这场比赛没打，但是吧赛时看了下题，和室友口胡了下正解是sqrt(a)+sqrt(b)时间计算出某对数的所有因数，设去重后一共有x个，之后for一遍所有对，总复杂度是

 

然后早上一写，submit，TLE on test99

woc？？？t最后一组？？？？

 

稍微再想一下我们可以发现，由于1e9内某些数的因子数量或超过1e3,例如{1889727840,1715313600},总个数x去重后大概有2e3多点

这样的话时间就是3e8多点，很容易被卡

 

那么怎么解决呢-----只遍历素因子就好了，素因子只有logn个，那么总复杂度就是了

对于所有因子，他们等效于他们的素因子，所以可以直接用素因子去遍历.

 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int readn()
{
    int x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    return x;
}
vector<pair<int,int> > vp;
set<int> st;
int main()
{
    int n=readn();
    vp.clear(),st.clear();
    for(int i=0;i<n;i++)
    {
        int a=readn(),b=readn();
        vp.push_back(make_pair(a,b));
    }
    if(vp[0].first!=1) st.insert(vp[0].first);
    if(vp[0].second!=1) st.insert(vp[0].second);
    for(int i=2;i*i<=vp[0].first;i++)
    {
        if(vp[0].first%i==0)
        {
            st.insert(i);
            while(vp[0].first%i==0) vp[0].first/=i;
        }
    }
    for(int i=2;i*i<=vp[0].second;i++)
    {
        if(vp[0].second%i==0)
        {
            st.insert(i);
            while(vp[0].second%i==0) vp[0].second/=i;
        }
    }
    if(vp[0].first!=1) st.insert(vp[0].first);
    if(vp[0].second!=1) st.insert(vp[0].second);
    int flag=1;
    for(auto x:st)
    {
        flag=1;
        for(int i=1;i<n;i++)
        {
            if(vp[i].first%x==0||vp[i].second%x==0) continue;
            else
            {
                flag=0;
                break;
            }
        }
        if(flag) return printf("%d\n",x)*0;
    }
    printf("-1\n");
}

 

但是实际上，原来的做法是可以卡过去的，1466ms，cf神仙机orz

 

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int a[maxn];
int b[maxn];
vector<int> v;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i*i<=a[0];i++)
    {
        if(a[0]%i==0)
        {
            if(i!=1) v.push_back(i);
            if(a[0]!=i) v.push_back(a[0]/i);
        }
    }
    for(int i=1;i*i<=b[0];i++)
    {
        if(b[0]%i==0)
        {
            if(i!=1) v.push_back(i);
            if(b[0]!=i) v.push_back(b[0]/i);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(auto x:v)
    {
        int flag=1;
        for(int i=1;i<n;i++)
        {
            if(a[i]%x&&b[i]%x)
            {
                flag=0;
                break;
            }
        }
        if(flag) return printf("%d\n",x)*0;
    }
    return printf("-1\n")*0;
}