提高-USB迷|专注于互联网分享

提高

一、题目分析

基本要求：求N个数的最大公约数和最小公倍数。

      1.程序风格良好(使用自定义注释模板)2.提供友好的输入输出，并进行输入数据的正确性验证。

提高要求：已知正整数a0,a1,b0,b1，设某未知正整数x满足：

1.x和a0的最大公约数是a1；

2.x和b0的最小公倍数是b1。

求出满足条件的正整数X。

输入格式

 输入第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。

输出格式

输出共n行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的x，请输出0；

若存在这样的x，请输出满足条件的x的个数。

二、算法构造

①构造用辗转相除法求最大公约数的子函数和求最小公倍数的子函数；

②在主函数中用if语句使用户可以根据自己的需求来选择功能；

③当m=0时，求最大公约数和最小公倍数，用while循环语句使在结束时提示是否继续计算，定义两个数组，使用随机函数将产生的随机数存储在数组中，使用for循环分别调用子函数，求出最大公约数和最小公倍数；

④当m=1时，解决最大公约数和最小公倍数之间的逆序问题，求符合条件的x的个数，提示输入需求数的组数，输入四个整数，并且四个整数符合题目要求，例如：输入组数为2，第一组数据为41
1 96 288，第二组数据为95 1 37 1776。使用if语句写出x应该满足的条件，并且用sum记录个数，最后输出sum。

三、算法实现

package 倩;import
java.util.Scanner;public class work {public static int GCD(int a,int b){//求最大公约数return
b==0?a:GCD(b,a%b);}public static int LCD(int m,int n){//求最小公倍数int t;t=GCD(m,n);int
result=m*n/t;return
result;}public static void
main(String[] args){int m;int
flag=1; //标记System.out.println("请选择你需要的算法");System.out.println("0----计算多个数的最大公约数和最小公倍数");System.out.println("1----最大公约数和最小公倍数之间的逆序");Scanner w=new
Scanner(System.in);m=w.nextInt();if(m==0){       //当m=0时执行计算最大公约数和最小公倍数的算法while(flag==1){int n,i,t;int[] a;a=new int[100];//数组长度int[] b;b=new int[100];System.out.println("请输入组数");Scanner k=new
Scanner(System.in);n=k.nextInt();for(i=0;i<n;i++){     //使用随机函数a[i]=(int)(Math.random()*100+1);}System.out.print("随机组数为：");for(i=0;i<n;i++){    //输出随机函数System.out.print("\t"+a[i]);}System.out.print("\n");for(i=0;i<n;i++){b[i]=a[i];     //将数组a的值复制给数组b}//计算最大公约数for(i=0;i<n-1;i++){b[i+1]=GCD(b[i],b[i+1]);}System.out.print("最大公约数为："+b[n-1]);System.out.print("\n");//计算最小公倍数for(i=0;i<n-1;i++){a[i+1]=LCD(a[i],a[i+1]);}System.out.print("最小公倍数为："+a[n-1]);System.out.print("\n");System.out.print("1---继续\n2---退出\n");Scanner s=new
Scanner(System.in);t=s.nextInt();if(t!=1){flag=0;}}}else{//当m=1时，执行最大公约数和最小公倍数之间的逆序算法int T;System.out.print("请输入组数\n");Scanner j=new Scanner(System.in);T=j.nextInt();//输入组数while(T--!=0){int
a0,a1,b0,b1;System.out.println("请输入四个数据");Scanner f=new Scanner(System.in);a0=f.nextInt();a1=f.nextInt();b0=f.nextInt();b1=f.nextInt();int
p=a0/a1,q=b1/b0,sum=0;//判断条件for(int x=1;x*x<=b1;x++){if(b1%x==0){           //x是b1的一个因数if(x%a1==0&&GCD(x/a1,p)==1&&GCD(q,b1/x)==1)
sum++;int
y=b1/x;         //y是另一个因数 if(x==y)
continue; if(y%a1==0&&GCD(y/a1,p)==1&&GCD(q,b1/y)==1)
sum++;}}System.out.println("符合条件的为："+sum);}}}
}

四、调试及测试截屏

五、总结
求最大公约数和最小公倍数是上次写过作业的，因此相对来说好写一点，只不过这次求的是多个数的，将辗转相除法写在子函数里面，在主函数中调用就好了；Hankson趣味问题：一定要读懂题目，要不然都不知道应该干什么，这个题中要用一些数学公式gcd（b1/b0,b1/x）=1来求出满足条件的x。在for循环语句中调用求最大公约数的子函数，最后输出符合条件的x的个数。

提高