东莞建站模板大全,浙江建设职业继续教育学院网站,dedecms 网站地图xml,谷建网站建设模板欧几里得算法
只需要记住一个公式#xff08;不需要推导#xff0c;这就是数论的基础知识#xff09;#xff1a; step1#xff1a;
判断小括号内右边的数字 b 是否为0#xff0c;如果为0#xff0c;输出小括号左边的数字 a #xff0c;就是一开始要求的两个数的最大…欧几里得算法
只需要记住一个公式不需要推导这就是数论的基础知识 step1
判断小括号内右边的数字 b 是否为0如果为0输出小括号左边的数字 a 就是一开始要求的两个数的最大公约数
step2
如果 b ! 0递归进入 gcd(b,a%b)这样一直缩小小括号右边的数字直到这个右边的数字为0那么此时左边的数就是一开始要求的两个数的最大公约数 题目如下
给定 n 对正整数 ai,bi请你求出每对数的最大公约数。
输入格式
第一行包含整数 n。
接下来 n 行每行包含一个整数对 ai,bi
输出格式
输出共 n 行每行输出一个整数对的最大公约数。
数据范围
1≤n≤105 1≤ai,bi≤2×109 代码如下
#includeiostream
#includecstringusing namespace std;int n;int gcd(int a,int b)
{if(b 0)return a;elsegcd(b,a%b);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n;while(n--){int a;int b;cin a b;cout gcd(a,b) endl;}return 0;
}
1模拟过程 2性质
