数论基础题.ppt

描述：小明被一个问题给难住了，现在需要你帮帮忙。问题是：给出两个正整数，求出它们的最大公约数和最小公倍数。 输入：第一行输入一个整数n（0n=10000)，表示有n组测试数据;随后的n行输入两个整数i,j（0i,j=32767)。输出：输出每组测试数据的最大公约数和最小公倍数 /JudgeOnline/problem.php?pid=40 基础题1：公约数 公倍数 #include?stdio.h?? ?? int?GCD(int?a,?int?b){?? ????if(a??b){?? ????????return?GCD(b,a);?? ????}?? ????if(b?==?0){?? ????????return?a;?? ????}?? ????else{?? ????????return?GCD(b,?a?%?b);?? ????}?? }?? ??? int?main?()?? {?? ????int?N,M,a,b;?? ????scanf(%d,N);?? ????while?(N--){?? ????????scanf(%d?%d,a,b);?? ????????M?=?GCD(a,b);?? ????????printf(%d?%d\n,M,a?*?b?/?M);?? ????}?? ????return?0;?? }?? ?? 练习：最小公倍数 /showproblem.php?pid=1019 描述：The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. 输入：Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. 输出： 分析：求n个数的最小公倍数我们最容易想到的思路就是求出两个数的最小公倍数，然后再用这个最小公倍数与第三个数球最小公倍数，依次下去就可以求出n个数的最小公倍数了。至于两个数的最小公倍数我们从上面的习题中已经可以知道方法了。a*b=gcd(a,b)*lcm(a,b);另一思路：短除法 #include stdio.h int gcd(int x,int y) { return x?gcd(y%x,x):y; } int main() { int i,j,n,m,ret,tem; scanf(%d,n); while(n--) { scanf(%d,m); scanf(%d,ret); m--; while(m--) { scanf(%d,tem); ret=ret/gcd(ret,tem)*tem; } ? printf(%d\n,ret); } } 基础题2：判断二元一次方程有没有整数解 描述： 已知二元一次方程?a*x+b*y=n，?判断这个二元一次方程有没有整数解，x,y为未知数，其中a，b，n都为整数且不等于零，同时满足0a,b,n2^16-1。 输入：第一行有一个整数0n=1000000表示有?n组测试数据,接下来的每一行有三个整数分别是a,b,n 输出： 整数x和y使得方程有解，输出“Yes”，否则输出“No” 样例输入 22?4?23?9?7 样例输出 Yes No #includestdio.hint?GCD(int?a,?int?b){?? ????if(a??b){?? ????????return