題目背景 眾所周知，我們稱g是a的約數，當且僅當g是正數且a mod g = 0。 眾所周知，若g既是a的約數也是b的約數，我們稱g是a、b的一個公約數。 眾所周知，a、b最大的那個公約數就叫最大公約數。 題目描述 現在對於給定的兩個正整數a、b，你需要求出它們次大的公約數（second great ...
題目背景
眾所周知，我們稱g是a的約數，當且僅當g是正數且a mod g = 0。
眾所周知，若g既是a的約數也是b的約數，我們稱g是a、b的一個公約數。
眾所周知，a、b最大的那個公約數就叫最大公約數。
題目描述
現在對於給定的兩個正整數a、b，你需要求出它們次大的公約數（second greatest common divisor）。
輸入輸出格式
輸入格式：
第一行兩個正整數數a、b。
輸出格式：
第一行一個數，表示a、b的次大公約數。若a、b的公約數只有一個，則輸出-1。
輸入輸出樣例
輸入樣例#1：2 3輸出樣例#1：
-1
說明
測試點1..4：a、b≤10^5
測試點1..10：1≤a、b≤10^9
這個題是求次大公約數， 我們可以YY一下， 當我們知道了一個數的最大公約數， 那麼他的次大公約數一定是最大公約數/它的最小質因數， 然而這個題是讓著求兩個數的次大公約數， 所以我們就不用篩素數了，畢竟直接掃是O(n)，篩素數也是O(n) 但是。。。 1也是兩個數的公約數！！！！！！！！！！！ 就這樣丟了十分啊啊還是我太年輕了1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=2000001; 8 const int INF = 1e8; 9 inline void read(int &n) 10 { 11 char c='+';int x=0;bool flag=0; 12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;} 13 while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();} 14 n=flag==1?-x:x; 15 } 16 int fir; 17 int sed; 18 int ans; 19 bool flag; 20 int gcd(int a,int b) 21 { 22 if(b==0) return a; 23 else return gcd(b,a%b); 24 } 25 int main() 26 { 27 //freopen("a.in","r",stdin); 28 //freopen("c.out","w",stdout); 29 int a,b; 30 read(a);read(b); 31 int g=gcd(a,b); 32 for(int i=2;i<=g-1;i++) 33 if(g%i==0) 34 { 35 ans=g/i; 36 break; 37 } 38 if(ans==0&&g!=1) cout<<"1"; 39 else cout<<(ans==0?-1:ans); 40 return 0; 41 }
