CF1025B Weakened Common Divisor【数论/GCD/思维】

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define mod 998244353

#define pi acos(-1.0)

#define rep(i,x,n) for(int i=(x); i<(n); i++)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 1<<30;

const int maxn = 150000+3;

const double eps = 1e-8;

const int dx[] = {-1,1,0,0,1,1,-1,-1};

const int dy[] = {0,0,1,-1,1,-1,1,-1};

int dir[2]={-1,1};

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int t,n,m,d;

int cnt=0;

LL lcm(LL a, LL b)

{

    return a/__gcd(a,b)*b;

}

LL cal(LL n)

{

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

        if(n%i==0) return i;

    return n;

}

LL a,b,x,y;

int main()

{

    cin>>n>>a>>b;

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

    {

        cin>>x>>y;

        a=__gcd(x*y,a);

        b=__gcd(x*y,b);

    }

    if(a!=1)

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

    else if(b!=1)

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

    else puts("-1");

}

/*

2

3 1

1 1 2

3 2

1 1 2

【题意】

给定n对数，求一个WCD，它满足至少能被每对数中的一个整除，若不存在，输出-1。

【类型】数论

【分析】一开始的思路是求每对数的最小公倍数，然后把这n个最小公倍数求个gcd，然后取其最小因子即可。但这样因为TLE而FST了。后来想想也是，如果每对数中的两个数互质，那么他们的最小公倍数就是1e18左右的大小，求其最小因子的时间复杂度差不多就是1e9，肯定会T。比如下面这组样例：

2

1999999973 1999999943

1999999973 1999999943

其实正解想法差不多，就把第一对中的第一个数和后面每对的乘积求一个gcd，第二个数也和后面的每对的乘积求一个gcd，这样就保证这两个数都是小于等于2e9的，求其最小因子的复杂度<1e5，可行。

PS：其实并不需要求每对数的最小公倍数，求其乘积即可，因为乘积包括了每对数那2个数中的所有因子，且乘积的最小因子一定能被每对数那2个数中的1个整除。

【时间复杂度&&优化】

【trick】

【数据】
巴特西

CF1025B Weakened Common Divisor【数论/GCD/思维】

最新文章

热门文章
