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
这个题是求次大公约数，
我们可以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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录