首页 > 代码库 > BestCoder10 1001 Revenge of GCD(hdu 5019) 解题报告
BestCoder10 1001 Revenge of GCD(hdu 5019) 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5019
题目意思：给出 X 和 Y，求出 第 K 个 X 和 Y 的最大公约数。 例如8 16，它们的公约数依次为1 2 4 8，那么第 3 个 GCD(X, Y) = 2，也就是从后往前数第3个公共因子。
TLE思路：求出 X 的所有因子（从小到大开始存储），再从后往前枚举这些因子，检查是否也为 Y 的因子，统计到第 K 个数就是答案了......以为可以顺利通过，原来数据量还是非常大滴！！！
正确思路：先求出 X 和 Y 的最大公约数 r，然后再求出 r 的 所有因子，从后往前数第 K 个就是答案了。这样做的依据是， r 的所有因子一定为 X 和 Y 的公共因子，也就符合题目要求啦～～～
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 typedef __int64 ll; 9 const ll maxn = 1e6 + 5;10 ll X, Y, K, ansi;11 ll com_factor[maxn];12 13 ll gcd(ll x, ll y)14 {15 while (y)16 {17 ll r = x % y;18 x = y;19 y = r;20 }21 return x;22 }23 24 int main()25 {26 int T, cnt;27 while (scanf("%d", &T) != EOF)28 {29 while (T--)30 {31 scanf("%I64d%I64d%I64d", &X, &Y, &K);32 if (X < Y)33 swap(X, Y);34 ll r = gcd(X, Y);35 cnt = 0;36 for (ll i = 1; i*i <= r; i++)37 {38 if (r % i == 0)39 {40 com_factor[++cnt] = i;41 if (r/i != i)42 com_factor[++cnt] = r/i;43 }44 }45 sort(com_factor+1, com_factor+cnt+1);46 reverse(com_factor+1, com_factor+cnt+1);47 printf("%I64d\n", cnt < K ? -1 : com_factor[K]);48 }49 }50 return 0;51 }
BestCoder10 1001 Revenge of GCD(hdu 5019) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。