https://www.luogu.org/problem/show?pid=U10783

題目背景

眾所周知，我們稱g是a的約數(shù)，當(dāng)且僅當(dāng)g是正數(shù)且a mod g = 0。

眾所周知，若g既是a的約數(shù)也是b的約數(shù)，我們稱g是a、b的一個公約數(shù)。

眾所周知，a、b最大的那個公約數(shù)就叫最大公約數(shù)。

題目描述

現(xiàn)在對于給定的兩個正整數(shù)a、b，你需要求出它們次大的公約數(shù)（second greatest common divisor）。

輸入輸出格式

輸入格式：

?

第一行兩個正整數(shù)數(shù)a、b。

?

輸出格式：

?

第一行一個數(shù)，表示a、b的次大公約數(shù)。若a、b的公約數(shù)只有一個，則輸出-1。

?

輸入輸出樣例

輸入樣例#1：
2 3 輸出樣例#1：
-1

說明

測試點1..4：a、b≤10^5

測試點1..10：1≤a、b≤10^9

?

次大公約數(shù)=最大公約數(shù)/最小公因子

#include<cstdio> #include<algorithm> using namespace std; int gcd(int a,int b) { return !b ? a:gcd(b,a%b); } int main() {int a,b;scanf("%d%d",&a,&b);int g=gcd(a,b);if(g==1) { printf("-1"); return 0; }int t=min(a,b),p=0;for(int i=2;i*i<=t;i++)if(a%i==0 && b%i==0) { p=i; break; }if(!p) p=t;a/=p; b/=p;printf("%d",gcd(a,b)); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TheRoadToTheGold/p/7341589.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 U10783 名字被和谐了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。