Java 求最小公倍数 + 大数阶乘 + K-好数问题_bigdecimal求最小公倍数

2018年5月17日20:22:26   清理垃圾

最小公倍数的求法：

输入

输出

样例输入

30 105
87 92

样例输出

210
8004

代码：

package cugoj;
 
import java.util.Scanner;
 
/*
 * 求最小公倍数
 * 就是先求出最大公约数，然后用两个数之积除以最大公约数即可
*/
public class Main514B {
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        
            Scanner s1 = new Scanner(System.in); 
            
            while(s1.hasNextInt())
            {
                long a = s1.nextLong();  
                long b = s1.nextLong();  
                  
                long mod = a % b;  
                if(mod == 0)  
                {
                    System.out.println(a); 
                }
                  
                long result = a*b/getMaxMult(a, b);  
                System.out.println(result); 
            } 
            s1.close();
        }  
          
        private static long getMaxMult(long a, long b)
        {  
            long m = a % b;  
            while (m != 0) {  
                a = b;  
                b = m;  
                m = a % b;  
            }  
            return b;  
        }  
     
}

大数阶乘的问题：

题目描述

输入

输出

样例输入

5
3

样例输出

3
1

代码1使用biginteger

package bignumbers;
/*
 * 描述：用biginteger来实现大数阶乘
 * compareTo方法用来比较，小于则返回-1，等于则返回0，大于则返回1
 * biginteger对象的比较compareTo和equal有区别，前者是返回int值，后者是返回的布尔值
 * 最终证明在oj网站上运行会超时
 * */
 
import java.math.BigInteger;
import java.util.Scanner;
 
public class dashujiecheng {
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        Scanner s1=new Scanner(System.in);
        while(s1.hasNext())
        {
            BigInteger n=new BigInteger(s1.next()); //System.out.println(n);
            /*BigInteger a=BigInteger.ONE;
            BigInteger b=BigInteger.ONE;*/
            BigInteger a=new BigInteger("1");
            BigInteger b=new BigInteger("1");
 
            for (BigInteger i=new BigInteger("1");i.compareTo(n)<=0;i=i.add(a))//忘记将自加后的赋值了
            {
                b=b.multiply(i);
            }
            
            //System.out.println(b);
            System.out.println("这个阶乘结果的位数为 "+b.toString().length());
        }
        s1.close();
    }
 
}

代码2  使用log函数

package cugoj;
 
import java.math.BigDecimal;
import java.util.Scanner;
 
/*描述
 * 输入：
      每行输入1个正整数n， （0<n<1000 000）
       输出：
      对于每个n，输出n!的（十进制）位数。
分析：
      所谓n!的十进制位数，就是 log(n!)+1, 根据数学公式有：n!=1*2*3*.....*n;
     lg(n!)=lg(2)+......lg(n);
     
     这个方法在cugoj上头时间超时了
 * 
 * */
 
public class Main514E {
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        Scanner s1=new Scanner(System.in);
        
        while (s1.hasNext())
        {
            long n=s1.nextLong();
            double sum=0;
            
            
            for (long i=2;i<n+1;i++)
            {
                BigDecimal bigDecimal=new BigDecimal(Math.log10(i));
                sum=sum+bigDecimal.doubleValue();
            }
            
            System.out.println((int)sum+1);
        }
        s1.close();
 
    }
 
}

代码3  使用斯特林公式

package cugoj;
/*描述
 * 采用斯特林公式来计算大数阶乘的位数
 * */
import java.util.Scanner;
 
public class Main514E2 {
 
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        Scanner s1=new Scanner(System.in);
        
        while (s1.hasNext())
        {
            int n=s1.nextInt();
            int res=0;
            if(n==1)
            {
                System.out.println(1);
            }else {
                res=(int)(Math.log10(2.0*3.1415926*n)/2+n*Math.log10(n/2.71828182))+1;
                System.out.println(res);
            }
        }
        s1.close();
 
    }
 
}

关于K-好数的问题：

题目描述

输入

输出

样例输入

4 2

样例输出

7

提示代码

package cugoj;
/*描述
 *  题目描述
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。
输入
输入包含两个正整数，K和L。
输出
输出一个整数，表示答案对1000000007取模后的值。
样例输入
4 2
样例输出
7
 * 
 * */
 
import java.util.Scanner;
 
public class Main514F {
 
    final static int MOD = 1000000007;
 
    public static void main(String[] args)
    {
        Scanner s1 = new Scanner(System.in);
 
        while (s1.hasNext()) {
            int k = s1.nextInt();
            int l = s1.nextInt();
            int num = 0;
            int[][] nums = new int[l][k];
            for (int i = 0; i < l; i++)
                for (int j = 0; j < k; j++)
                    nums[i][j] = 0;
            for (int j = 0; j < k; j++)
                nums[0][j] = 1;
            for (int i = 1; i < l; i++)
                for (int j = 0; j < k; j++)
                    for (int x = 0; x < k; x++) {
                        if (x != j - 1 && x != j + 1) {
                            nums[i][j] += nums[i - 1][x];
                            nums[i][j] %= MOD;
                        }
                    }
            for (int j = 1; j < k; j++) {
                num += nums[l - 1][j];
                num %= MOD;
            }
            System.out.println(num);
        }
        s1.close();
 
    }
 
}

30 105
87 92

210
8004