小明很喜欢数对,又很喜欢GCD(最大公约数)。所以他想尽办法创造了一种全新的最大公约数:
给出若干个数对(ai,bi),如果一个最大的质数x可以整除每一个数对中的至少一个数字并且这个数字大于1,那么x就称为这些数对的N-GCD。
现在小明给了你一些数对,希望你可以算出它们的N-GCD。
第一行一个数字n,表示数对的个数。
接下来n行,每行两个数字,用一个空格分隔,表示一个数对。
满足1<=n <=150000,1<=ai,bi<=2 * 10^9。
一个数字,这些数对的N-GCD;若N-GCD不存在,那么输出-1。
3 2 2 3 6 7 8
2
2 18 12 3 24
3
import java.io.*; import java.lang.*; public class Main { private static StreamTokenizer st = new StreamTokenizer( new BufferedReader(new InputStreamReader(System.in))); private static int nextInt() { try { st.nextToken(); return (int)st.nval; }catch(IOException e) { throw new RuntimeException(e); } } public static boolean isPrime(long num) { for(int i = 2; i * i < num; i++) { if(num % i == 0) { return false; } } return true; } public static void main(String[] args) { int n = nextInt(); long[][] arr = new long[n][2]; long minimum = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { arr[i][0] = nextInt(); minimum = Math.min(minimum, arr[i][0]); arr[i][1] = nextInt(); minimum = Math.min(minimum, arr[i][1]); } long result = -1; long i = 2; while(i <= minimum) {//双重验证:整除+质数 boolean flag = true; for(int j = 0; j < n; j++) { if((arr[j][0] % i != 0) && (arr[j][1] % i != 0)) { flag = false; break; } } if(flag && isPrime(i)) { result = i; } i++; } System.out.println(result); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner s=new Scanner(System.in); int size=s.nextInt(); int min=Integer.MAX_VALUE; int[] firsts=new int[size]; int[] seconds=new int[size]; //读取数组并标记最小数。 可以放入一个数组内。这里为了方便理解用两个数组分开存放 for(int i=0;i<size;i++){ int first=s.nextInt(); int second=s.nextInt(); firsts[i]=first; seconds[i]=second; int temp=first>second?second:first; if(min>temp){ min=temp; } } while(min>1){ //是不是质数 if(!isPrimeNumber(min)){ min--; continue; } for(int i=0;i<size;i++){ if(firsts[i]%min!=0 && seconds[i]%min!=0){ min--; break; } //全数对扫描完成复核条件,直接输出 if(i==size-1){ System.out.println(min); return; } } } System.out.println(-1); } public static boolean isPrimeNumber(int num){ for(int i=2;i<num;i++){ if(num%i==0){ return false; } } return true; } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; /** * @Author: coderjjp * @Date: 2020-05-09 13:48 * @Description: 数对的N-GCD * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int eNum = Integer.valueOf(br.readLine()); int data[][] = new int[eNum][2]; long min = 0; String linex[]; for (int i = 0; i < eNum; i++) { linex = br.readLine().split(" "); data[i][0] = Integer.valueOf(linex[0]); data[i][1] = Integer.valueOf(linex[1]); if (i == 0) min = data[i][0]; min = Math.min(min, data[i][0]); min = Math.min(min, data[i][0]); } ArrayList<Integer> prime = new ArrayList<>(); for (int i = 2; i <= min; i++) if (isPrime(i)) prime.add(i); for (int i = 0; i < eNum; i++) for (int j = 0; j < prime.size(); j++) if (data[i][0] % prime.get(j) != 0 && data[i][1] % prime.get(j) != 0) prime.remove(j); if (prime.size() == 0) System.out.println(-1); else System.out.println(prime.get(prime.size() - 1)); } private static boolean isPrime(int a) { for(int i = 2; i <= Math.sqrt(a); i++) if (a % i == 0) return false; return true; } }