小明很喜欢数对,又很喜欢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.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.ArrayList; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); ArrayList<int[]> list = new ArrayList(n); int min = Integer.MAX_VALUE; for(int i = 0; i < n; i++){ String[] temp = br.readLine().trim().split(" "); int a = Integer.parseInt(temp[0]), b = Integer.parseInt(temp[1]); min = Math.min(min, Math.min(a, b)); list.add(new int[]{a, b}); } int factor = min; while(factor > 1){ if(!isPrime(factor)) { // 因子不是质数直接跳过本次循环 factor--; continue; } boolean flag = true; // 否则检验这个因子是否是N-GCD for(int i = 0; i < n; i++){ if(list.get(i)[0] % factor != 0 && list.get(i)[1] % factor != 0){ // 只要有一对数两个数都不能被factor整除,就退出循环 flag = false; break; } } if(flag) break; else factor--; } System.out.println(factor); } private static boolean isPrime(int x){ for(int i = 2; i < (int)Math.ceil(Math.sqrt(x)); i++){ if(x % i == 0) return false; } return true; } }
//case通过率90% 的解决思路: 时间复杂度最高是在main()的循环处 //并且 判断是否为质数的复杂度 高于 判断某一质数是否能整数每行中的某个值 // 之前先判断是否为质数,然后判断是否能整除每行当中的某个值,通过率始终为90% // 改变顺序:先判断是否能整除,然后判断是否为质数,全部通过 # include<iostream> # include<algorithm> using namespace std; bool isZhiShu(long long value){ for(long long i=2; i<=sqrt(value); i++) if(value%i==0) return false; return true; } int main(){ int n; cin>>n; long long arr[n][2], limit=2000000001; for(int i=0; i<n; i++){ cin>>arr[i][0]>>arr[i][1]; limit = min(limit, max(arr[i][0], arr[i][1])); } int j=0; for(long long i=limit; i>=2; i--){// 从最大值开始依次遍历 for(j=0; j<n; j++) if(arr[j][0]%i!=0 && arr[j][1]%i!=0) break; if(j==n && isZhiShu(i)){ cout<<i<<endl; return 0; } } cout<<-1<<endl; return 0; }
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; } }
/*您的代码已保存 运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出case通过率为70.00%*/import java.util.*; public class Main{ public static void main(String[] org){ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); scan.nextLine(); int[] s = new int[n*2]; int[] s1 = new int[2*n]; for(int i=0;i<2*n;i++){ s[i] = scan.nextInt(); } s1 = s.clone(); int x=-1; for(int i=2;i<=getMin(s1);i++){ int h=0; if(isZhiShu(i)){ for(int j=0;j<n*2;j++){ if(isZhengChu(s[j],s[j+1],i)){ h++; if(h==n){ if(x<i){ x=i; } } } j++; } } } System.out.println(x); } public static int getMin(int[] s1){ Arrays.sort(s1); return s1[0]; } public static boolean isZhiShu(int x){ for(int i=2;i<x;i++){ if((x%i)==0){ return false; } } return true; } public static boolean isZhengChu(int a,int b,int x){ if((a%x)==0||(b%x)==0){ return true; }else return false; } }
/*对任意一组分解质因数(这里选和最小的),遍历所有组,不满足条件(整除任意组的至少一个数)的删除 最后看剩下的有无,没有-1.有输出最大的*/ #include <bits/stdc++.h> #define LL long long using namespace std; const int AX = 2e5 + 666 ; struct Node{ LL x ; LL y ; bool operator < ( const Node &a )const{ return ( x + y ) < ( a.x + a.y ) ; } }a[AX]; set<LL>s ; void get_PrimeFac( LL x ){ for( LL i = 2 ; i * i <= x ; i++ ){ if( x % i == 0 ){ s.insert(i) ; while( x % i == 0 ){ x /= i ; } } } if( x > 1 ) s.insert(x) ; } int main(){ int n ; scanf("%d",&n) ; LL x , y ; for( int i = 0 ; i < n ; i++ ){ scanf("%lld%lld",&a[i].x,&a[i].y) ; } sort( a , a + n ) ; get_PrimeFac(a[0].x); get_PrimeFac(a[0].y); set<LL>::iterator it , tmp ; if( s.size() ){ for( int i = 1 ; i < n ; i++ ){ it = s.begin() ; //放错位置找了半天- -。 while( it != s.end() ){ if( ( a[i].x % (*it) ) && ( a[i].y % (*it) ) ){ tmp = it ; it++ ; s.erase(tmp) ; }else it++ ; } } } if( !s.size() ){ cout << -1 << endl; }else{ it = s.end() ; it--; cout << *it << endl; } return 0 ; }
#include <bits/stdc++.h> using namespace std; bool P(int n){ for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } int main(){ int n; cin>>n; int a[n],b[n],m=INT_MAX; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; m = min(m, a[i]); m = min(m, b[i]); } while(m>1){ if(((m&1)==0 && m!=2) || (!P(m))){ m--; continue; } bool flag = true; for(int i=0;i<n;i++){ if(!((a[i]%m==0) || (b[i]%m==0))){ flag = false; break; } } if(flag) break; else m--; } cout<<((m==1)?-1:m)<<endl; return 0; }
(pair[0][0]%i==0 || pair[0][1]%i==0) && isPrime(i)添加到一个队列当中,然后再遍历pair,
import java.io.*; import java.util.ArrayList; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); int[][] pair=new int[n][2]; for(int i=0;i<n;i++){ String[] line=br.readLine().split(" "); pair[i][0]=Integer.parseInt(line[0]); pair[i][1]=Integer.parseInt(line[1]); } ArrayList<Integer> GCD=new ArrayList<>(); for(int i=Math.max(pair[0][0],pair[0][1]);i>1;i--){ if((pair[0][0]%i==0 || pair[0][1]%i==0) && isPrime(i)){ GCD.add(i); } } int index=0; int len=GCD.size(); for(int i=1;i<n;i++){ if(pair[i][0]%GCD.get(index)==0 || pair[i][1]%GCD.get(index)==0){ continue; } while(index<len && pair[i][0]%GCD.get(index)!=0 && pair[i][1]%GCD.get(index)!=0){ index++; } if(index==n){ System.out.println(-1); return; } } System.out.println(GCD.get(index)); } public static boolean isPrime(int num){ for(int i=2;i<=Math.sqrt(num);i++){ if(num%i==0){ return false; } } return true; } }
n = int(input().strip()) nums = [] min_num = float("inf") for _ in range(n): num_group = list(map(int, input().strip().split(" "))) min_num = min(min_num, min(num_group)) nums.append(num_group) def is_ok(div): for num2 in nums: if num2[0] % div != 0 and num2[1] % div != 0: return False return True tmp = min_num if tmp > 2 and tmp % 2 == 0: # 如果最小值是大于2的偶数,减一 tmp -= 1 status = 0 while not status and tmp > 1: # 不是质数,或者不能满足数对整除,则一直往下减。 status = 1 i = int(pow(tmp, 0.5))+1 # 结束条件,没有奇数可以被大于它的平方根的数整除,所以往后不需要在检查。 for j in range(3, i, 2): # 步长依旧是二,奇数tmp不可以被偶数i整除。 if (tmp % j) == 0: status = 0 break if status: if is_ok(tmp): break else: status = 0 tmp -= 2 # 每次减2,还是因为偶数不是质数 if status: print(tmp) else: print(-1)
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; bool isP(int n){ for (int j=2;j<=n/2;++j){ if (n%j==0) return 0; } return 1; } vector<int> get(int a,int b){ vector<int> ysy; //ysy.push_back(2); for (int j=2;j<=max(a,b);++j){ if ((a%j==0 || b%j==0 )&& isP(j)) ysy.push_back(j); } return ysy; } int n,a,b; int main(){ scanf("%d",&n); int dp[n][2]; vector<int> ans; long mymin=2000000001; for (int i=0;i<n;++i){ scanf("%d %d",&dp[i][0],&dp[i][1]); if (mymin>max(dp[i][0],dp[i][1])){ a=dp[i][0]; b=dp[i][1]; mymin=max(dp[i][0],dp[i][1]); } } ans=get(a,b); int i=0; for (;i<n;++i){ if (ans.size()==0) break; a=dp[i][0]; b=dp[i][1]; vector<int> tmp; vector<int>::iterator iter; for (iter=ans.begin();iter!=ans.end();iter++){ if (a%*iter==0 or b%*iter==0) tmp.push_back(*iter); } ans=tmp; } if (i==n) cout<<ans.back()<<endl; else cout<<-1<<endl; }
#include <iostream> #include <vector> #include <math.h> using namespace std; bool isPrime(int num) { if (num % 6 != 1 && num % 6 != 5) { return false; } for (int i = 6; i <= sqrt(num) + 1; i += 6) { if (num % (i - 1) == 0 || num % (i + 1) == 0) return false; } return true; } int main() { bool isPrime(int num); int eNum = 0; scanf("%d", &eNum); int** data = new int*[eNum]; long res = -1; long min = 0; for (int i = 0; i < eNum; i++) { data[i] = new int[2]; scanf("%d %d", &data[i][0], &data[i][1]); if (i == 0) min = data[i][0]; min = min < data[i][0] ? min : data[i][0]; min = min < data[i][1] ? min : data[i][1]; } vector<int> prime = { 2,3 }; for (int i = 6; i < min; i += 6) { if (isPrime(i - 1)) prime.push_back(i - 1); if (isPrime(i + 1)) prime.push_back(i + 1); } for (int i = 0; i < eNum; i++) { for (int j = 0; j < prime.size(); j++) { if (data[i][0] % prime[j] != 0 && data[i][1] % prime[j] != 0) prime.erase(prime.begin() + j); } } if (prime.size() == 0) cout << -1 << endl; else cout << prime[prime.size() - 1] << endl; }
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 sys n = int(input()) pairs = [] for line in sys.stdin: pairs.append(list(map(int, list(line.split())))) def isprime(n): for i in range(2, n): if n%i == 0: return False return True def cal(n): res = [] for i in range(2, n + 1): if n%i == 0 and isprime(i): res.append(i) return res def solution(l): res = -1 for n in l: for a, b in pairs: if not (a%n == 0&nbs***bsp;b%n == 0): break else: return n return -1 a, b = min(pairs, key=lambda x:max(x)) l = cal(a) + cal(b) l.sort(reverse=True) print(solution(l))
在读取数字的时候顺便计算下最小值min,之后找出[2,min]
之间的素数,并从大到小遍历,判断该数能否整除除nums
数组中每一个数对中的任意一个值。
from math import sqrt def is_prime(a): for i in range(2,int(sqrt(a)+1)): if a%i==0: return False return True N = int(input()) nums = [] min_val = 1e9 for i in range(N): val1,val2 = list(map(int,input().split())) min_val = min(min_val,val1,val2) nums.append([val1,val2]) primes = [] res = 1e9 for i in range(min_val,1,-1): if is_prime(i): primes.append(i) for val in primes: satisfied = True for i in range(N): if nums[i][0]%val!=0 and nums[i][1]%val!=0: satisfied = False break if satisfied: res = val break print(res) if res!=1e9 else print(-1)
#include <bits/stdc++.h> using namespace std; bool isPrime(long long n) // 判断n是不是质数 { for(int i=2;i<=sqrt(n);i++) //注意从2开始 终止条件是根号 if(n%i==0) return false; return true; } int main() { long long n,res=-1; cin>>n; vector<vector<long long>>num; vector<long long> temp(2); long long minNum=LONG_LONG_MAX; for(int i=0;i<n;i++) { cin>>temp[0]; cin>>temp[1]; minNum=min(minNum,min(temp[0],temp[1])); //找到数对中的最小值 num.push_back(temp); } for(long long j=minNum+1;j>=2;j--) //从最小值开始从后往前 { bool breakLoop=false; for(auto vec:num) { if(vec[0]%j!=0&&vec[1]%j!=0) //如果都不能整除则跳出 { breakLoop=true; break; } } if(breakLoop) continue; if(isPrime(j)) //是质数,找到答案 { res=j; break; } } cout<<res<<endl; }
思路不是很难,但minValue的设置不熟悉,搞了很久才发现是最小值的初值给的有问题,坑 #include <iostream> #include <vector> #include <algorithm> using namespace std; int findGCD(int n) { int ans = -1; vector<vector<int>> nums(n, vector<int>()); int minValue = 2000000001; //cout << n << endl; for (int i = 0; i < n; i++) { int v1 = 0; int v2 = 0; cin >> v1 >> v2; //cout << v1 << " " << v2 << endl; nums[i].push_back(v1); nums[i].push_back(v2); //cout << minValue << endl; minValue = min(minValue, max(v1, v2)); //cout << minValue << " " << i << endl; } //获取可能的非质数公约数 int numsGcds = minValue; //不能进行开方,因为数字本身可能为质数 vector<int> gcds(numsGcds+1, 1); gcds[0] = 0; gcds[1] = 0; //cout << numsGcds << "ji " << endl; for (int i = 2; i <= numsGcds; i++) { if (gcds[i]) { gcds[i] = i; for (int j = i + i; j <= numsGcds; ) { gcds[j] = 0; j = j + i; } } } for (int i = 0; i < gcds.size(); i++) { if (gcds[i]) { int tempAns = gcds[i]; //cout << tempAns << endl; bool ok = true; for (int j = 0; j < nums.size(); j++) { if (nums[j][0] % tempAns == 0 || nums[j][1] % tempAns == 0) { continue; } else { ok = false; break; } } if (ok) { ans = max(ans, tempAns); //cout << ans << endl; } } } return ans; } int main() { int n; cin >> n; int ans = findGCD(n); cout << ans << endl; //system("Pause"); return 0; }
#include<bits/stdc++.h> using namespace std; vector<int>v; void func(vector<int>& v){ int n = v.size()-1; for(int i=1;i<=n;++i){ if(i&1) v[i]=1; else v[i] = 0; } for(int i=3;i<=n;++i) { if(v[i]){ for(int j=i+i;j<=n;j+=i) v[j]=0; } } } int main(){ int n; cin>>n; vector<int>A(n); vector<int>B(n); // m的可取值范围从每组的最大值的集合中的最小值递减到2 int m = INT_MAX; for(int i=0;i<n;++i){ cin>>A[i]>>B[i]; m = min(m,max(A[i],B[i])); } //素数筛法 确定2~m的素数 v.resize(m+1); func(v); v[2]=1; while(m>1){ if(!v[m]) { if(m&1) m-=2; else m-=1; continue; } int i; for(i=0;i<n;++i){ if(!(A[i]%m==0||B[i]%m==0)) { break; } } if(i!=n) m--; else break; } cout<<(m==1?-1:m)<<endl; return 0; }
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; } }