提高 - 源码之家

一、题目分析

基本要求：求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的个数。

提高

相关推荐