首页 > 试题广场 >

N-GCD

[编程题]N-GCD

小明很喜欢数对，又很喜欢GCD(最大公约数)。所以他想尽办法创造了一种全新的最大公约数：

给出若干个数对(a_i,b_i)，如果一个最大的质数x可以整除每一个数对中的至少一个数字并且这个数字大于1，那么x就称为这些数对的N-GCD。

现在小明给了你一些数对，希望你可以算出它们的N-GCD。


第一行一个数字n，表示数对的个数。
接下来n行，每行两个数字，用一个空格分隔，表示一个数对。
满足1<=n <=150000,1<=a_i,b_i<=2 * 10^9。

一个数字，这些数对的N-GCD；若N-GCD不存在，那么输出-1。

示例1

输入

示例2

2
18 12
3 24

算法知识视频讲解

bandiaoz

发表于 2024-12-26 14:08:59

解题思路这是一道数论题目，主要思路如下： N-GCD的定义：对于一组数对，如果存在一个质数可以整除每个数对中的至少一个数且大于1，则就是这些数对的 N-GCD 求解步骤：找出所有数对中最小的数生成不超过这个最小数的所有质数检查每个质数是否满足N-GCD的条件展开全文

ls.joshua

发表于 2020-03-25 17:35:46

joshua分享简单题：先打素数表，再从最小值的那个开始从最大素数开始判断 #include <bits/stdc++.h> using namespace std; int main(void) { int n, i, j, tMin = 0x7fffffff; v 展开全文

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师动态规划网易 2019 拼多多集团-PDD 数学 Java工程师

上传者：小小

难度：

24条回答 31收藏 7542浏览

查看代码

N-GCD

扫一扫，把题目装进口袋