1025B.Weakened Common Divisor

题目链接：http://codeforces.com/problemset/problem/1025/B?csrf_token=4e6bc03612af9704b1b5d04a1252156d

题目大意：给出n对数字，要求求一个数，使得这个数是每对数中至少一个数的因子，题目可能出现多个符合要求的数，所以输出一个符合的数就行了。

思路：将第一对数字a,b单独拿出来，对其之后输入的数字对（x,y）的积x*y用__gcd()求他们的最大公因子，并将结果重新覆盖a,b，最后，因为我们是对x*y与a或b求的最大公因子，为了防止出现因子恰好分别出现在x与y中，而x*y却恰好是a或b的倍数的情况出现，我们最后再求一次其最小因子。

代码：

#include
#include
#include
#include
typedef long long ll;
using namespace std;ll f(ll k)
{for(int i = 2; i <= sqrt(k);i++){if(k % i == 0)return i;}return k;
}
int main()
{ll n,a,b,x,y;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(max(a,b)==1){cout<<"-1"<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！