创办一个网站要多少钱,linux做网站配置,十大经典案例,手机网站改版【题目来源】https://www.acwing.com/problem/content/874/【题目描述】 给定 n 对正整数 ai,bi#xff0c;请你求出每对数的最大公约数。【输入格式】 第一行包含整数 n。 接下来 n 行#xff0c;每行包含一个整数对 ai,bi。【输出格式】 输出共 n 行#xff0c;每行输出一…【题目来源】https://www.acwing.com/problem/content/874/【题目描述】 给定 n 对正整数 ai,bi请你求出每对数的最大公约数。【输入格式】 第一行包含整数 n。 接下来 n 行每行包含一个整数对 ai,bi。【输出格式】 输出共 n 行每行输出一个整数对的最大公约数。【数据范围】 1≤n≤10^5, 1≤ai,bi≤2×10^9【输入样例】 2 3 6 4 6【输出样例】 3 2【算法代码辗转相除法 ← 递归】
#include bits/stdc.h
using namespace std;int gcd(int a,int b) {if(b0) return a;else return gcd(b,a%b);
}int main() {int n;cinn;while(n--) {int a,b;cinab;coutgcd(a,b)endl;}return 0;
}/*
in:
2
3 6
4 6out:
3
2
*/
【算法代码更相减损法 ← 非递归】
#include bits/stdc.h
using namespace std;int gcd(int a,int b) {while(a!b) {if(ab) a-b;else b-a;}return a;
}int main() {int n;cinn;while(n--) {int a,b;cinab;coutgcd(a,b)endl;}return 0;
}/*
in:
2
3 6
4 6out:
3
2
*/
【算法代码利用 algorithm 包中自带的函数 __gcd()】
#include bits/stdc.h
using namespace std;int main() {int n;cinn;while(n--) {int a,b;cinab;cout__gcd(a,b)endl;}return 0;
}/*
in:
2
3 6
4 6out:
3
2
*/
【算法代码依据数学定义自编 gcd() 函数】 本代码中依据数学定义自编 gcd() 函数。但由于本题数据规模太大显然会超时TLE。
#include bits/stdc.h
using namespace std;int gcd(int a,int b) {for(int imin(a,b); i2; i--) {if(a%i0 b%i0) return i;}
}int main() {int n;cinn;while(n--) {int a,b;cinab;coutgcd(a,b)endl;}return 0;
}/*
in:
2
3 6
4 6out:
3
2
*/
【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/110733164https://www.acwing.com/solution/content/98177/
