【数论】hdu 5019 Revenge of GCD

小灰灰 2024-03-30 11:46 67阅读 0赞

[Problem - 5019 (hdu.edu.cn)][Problem - 5019 _hdu.edu.cn]

题意：

给出整数x、y、k，求x、y的第k大公约数。

思路：

其实这道题是在考怎么遍历x和y的所有公因数

只需遍历gcd(x,y)的约数即可

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int x,y,k;
    void solve(){
        vector<int> v;
        cin>>x>>y>>k;
        int d=__gcd(x,y);
        for(int i=1;i<=d/i;i++){
            if(d%i==0){
                v.push_back(i);
                if(i!=d/i) v.push_back(d/i);
            }
        }
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        if(k-1>v.size()-1) cout<<-1<<'\n';
        else cout<<v[k-1]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

**总结：**

**遍历x和y的所有公因数只需遍历gcd(x,y)的约数即可**

其实这样比较好理解

**由于：**

![30afdc92e02643a28f95b35117c20a90.png][]

**当我们的指数取的比min还小时，就是普遍的公约数了，这样看，公约数就一定是最大公约数的约数**

**可以拓展一下：当指数取得比max还大时，最小公倍数一定是公倍数的倍数**

[Problem - 5019 _hdu.edu.cn]: https://acm.hdu.edu.cn/showproblem.php?pid=5019
[30afdc92e02643a28f95b35117c20a90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/06eaed7325f04c39a579daae7a8ef25c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读

相关【数论】hdu 5019 Revenge of GCD

[Problem - 5019 (hdu.edu.cn)][Problem - 5019 _hdu.edu.cn] 题意：给出整数x、y、k，求x、y的第k大公约数。

小灰灰/ 2024年03月30日 11:46/ 0 赞/ 68 阅读

相关 UVA 12333 Revenge of Fibonacci

题目链接：[https://vjudge.net/problem/UVA-12333][https_vjudge.net_problem_UVA-12333] 题意摘自《算法

川长思鸟来/ 2023年06月04日 14:54/ 0 赞/ 65 阅读

相关 Hdu 1695 GCD (数论容斥原理)

参考了：[HDU 1695 GCD 【数论，容斥原理】 - 脑残 - 博客频道 - CSDN.NET][HDU 1695 GCD _ - _ - _ - CSDN.NET]

落日映苍穹つ/ 2022年08月26日 08:10/ 0 赞/ 160 阅读

相关 HDU 5495 LCS（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5495 参考博客： http://blog.csdn.net/queue

小咪咪/ 2022年08月09日 01:59/ 0 赞/ 157 阅读

相关 HDU 5398 GCD Tree

这题可以基本说是LCT的模板题目，几乎没什么多余的考虑。不像HDU 5333，那题除了用LCT维护最大生成树之外还有一些复杂的公式推算。对于多组数据，从1枚举到n，然后加

桃扇骨/ 2022年08月04日 05:26/ 0 赞/ 156 阅读

相关 HDU 5750 Dertouzos（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5750 题目大意：x能整除n，x就是n的positive proper div

谁借莪１个温暖的怀抱￠/ 2022年07月20日 12:15/ 0 赞/ 128 阅读

相关 hdu5726 GCD

GCD Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Othe

╰半夏微凉°/ 2022年07月18日 16:30/ 0 赞/ 168 阅读

相关 ACM 数论 Maximum GCD

滴，集训第二十三天打卡。转眼集训已经过去一半了，今天是数论基础。一眼看去，都是简单题，一题题做来，都是坑啊坑... UVA 11827 Maximum

爱被打了一巴掌/ 2022年06月10日 03:40/ 0 赞/ 175 阅读

相关 HDU 3988(数论)

问题描述: iSea is tired of writing the story of Harry Potter, so, lucky you, solving the fo

浅浅的花香味﹌/ 2022年05月31日 05:06/ 0 赞/ 179 阅读

相关 HDU - 2504- 又见GCD【数论+gcd 】题解

目录 1.题目 2.代码 1.题目有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a

逃离我推掉我的手/ 2021年07月25日 00:03/ 0 赞/ 380 阅读