U10783 名字被和谐了

题目背景

众所周知，我们称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

分析

可以证明，a,b的所有公约数都被组大公约数所包含，都是最大公约数的因数，所以先求出最大公约数，然后在最大公约数中在找次大公约数。

code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int Gcd(int x,int y)

 {

     if (y==) return x;

     return Gcd(y,x%y);

 }

 bool Isprime(int x)

 {

     for (int i=; i*i<=x; ++i)

     {

         if (x%i==) return false;

     }

     return true;

 }

 int main()

 {

     int d,x,y;

     scanf("%d%d",&x,&y);

     d = Gcd(x,y);

     if (d==)

     {

         printf("-1");

         return ;

     }

     if (Isprime(d))

     {

         printf("");

         return ;

     }

     for (int i=; ; ++i)

     {

         if (d%i==)

         {

             printf("%d",d/i);

             return ;

         }

     }

     return ;

 }

巴特西

U10783 名字被和谐了

U10783 名字被和谐了

题目背景

题目描述

输入输出格式

输入输出样例

说明

分析

code

最新文章

热门文章