HDU 5019 Revenge of GCD(数学)
of HDU 数学 gcd
2023-09-14 09:10:07 时间
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5019
Problem Description
In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (when at least one of them is not zero), is the largest positive integer
that divides the numbers without a remainder.
---Wikipedia
Today, GCD takes revenge on you. You have to figure out the k-th GCD of X and Y.
---Wikipedia
Today, GCD takes revenge on you. You have to figure out the k-th GCD of X and Y.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case only contains three integers X, Y and K.
[Technical Specification]
1. 1 <= T <= 100
2. 1 <= X, Y, K <= 1 000 000 000 000
Each test case only contains three integers X, Y and K.
[Technical Specification]
1. 1 <= T <= 100
2. 1 <= X, Y, K <= 1 000 000 000 000
Output
For each test case, output the k-th GCD of X and Y. If no such integer exists, output -1.
Sample Input
3 2 3 1 2 3 2 8 16 3
Sample Output
1 -1 2
Source
官方题解:
代码例如以下:
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef __int64 LL; vector<LL>v; LL GCD(LL a, LL b) { if(b == 0) return a; return GCD(b,a%b); } int main() { int t; LL x, y, k; scanf("%d",&t); while(t--) { v.clear(); scanf("%I64d%I64d%I64d",&x,&y,&k); LL tt = GCD(x,y); // printf("%I64d\n",tt); for(LL i = 1; i*i <= tt; i++) { if(tt%i == 0) { v.push_back(i); if(i*i != tt)//防止放入两个i v.push_back(tt/i); } } sort(v.begin(), v.end()); if(k > v.size()) printf("-1\n"); else printf("%I64d\n",v[v.size()-k]); } return 0; }
相关文章
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-01754: a table may contain only one column of type LONG ORACLE 报错 故障修复 远程处理
- ORA-19772: change tracking file name exceeds limit of string characters ORACLE 报错 故障修复 远程处理
- ORA-23474: definition of “string”.”string” has changed since generation of replication support ORACLE 报错 故障修复 远程处理
- ORA-25005: cannot CREATE INSTEAD OF trigger on a read-only view ORACLE 报错 故障修复 远程处理
- ORA-25315: unsupported configuration for propagation of buffered messages ORACLE 报错 故障修复 远程处理
- ORA-42302: definition of an Editioning view may not refer to remote tables ORACLE 报错 故障修复 远程处理
- ORA-54500: invalid combination of elements ORACLE 报错 故障修复 远程处理
- ORA-56864: Master Diskmon “stringstring” operation cannot complete because of a LIBCELL network error ORACLE 报错 故障修复 远程处理
- ORA-64110: XMLIndex: problems encountered during the gathering of statistics ORACLE 报错 故障修复 远程处理
- ORA-02705: osnpol: polling of communication channel failed ORACLE 报错 故障修复 远程处理
- ORA-14628: specification of bounds is inconsistent with LIST method ORACLE 报错 故障修复 远程处理
- Oracle VLDB: Unleashing the Power of Big Data(oraclevldb)
- Exploring the Sideways of Linux: Diving into the World of Linux Sid for Advanced Users!(linuxsid)
- Exploring the Contents of MySQL Data Tables: A Comprehensive Guide(mysql数据表内容)
- Exploring the Versatile World of Linux PDA: Features Applications and Advantages(linuxpda)
- 解锤OracleAS OF模式深入浅出(oracle as of)