【算法】最大最小公倍数、K好数

算法训练最大最小公倍数
时间限制：1.0s 内存限制：256.0MB

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。

这个题之前提到过是分几种情况讨论的。num=n(n-)，看num和第三个数是否同为奇偶，如果不是的最小公倍数就是n(n-1)*(n-2),如果不是的则考虑第三个数下滑一个为

n(n-1)(n-3)这时需要考虑n和（n-3）是不是3的倍数如果是则需将n-1，再重新考虑。这种方法比较麻烦。

我用的方法是穷举几个数就够了。哦，还有int和double类型都是装不下的，这是个坑。

代码：

import java.util.Scanner;

public class 最大最小公倍数 {

	public static void main(String[] args) {
		
		long max=0;
		Scanner sc=new Scanner(System.in);

		while(sc.hasNext()){
			int n=sc.nextInt();
			for (long i = n; i >n-10&&i>0; i--) {
				for (long j = i; j >n-10&&j>0; j--) {
					long num=i*j/gcd(i,j);
					for (long h = j; h >n-10&&h>0; h--) {
						long num2=num*h/gcd(h,num);
						if(num2>max){
							max=num2;
						}
					}
				}
			}
			System.out.println(max);
		}
	}

	private static long gcd(long i, long j) {
		if(i%j==0)
			return j;
		return gcd(j,i%j);
	}
}

算法训练 K好数
时间限制：1.0s 内存限制：256.0MB

问题描述
如果一个自然数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
数据规模与约定
对于30%的数据，KL <= 106；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

这个题，之前不太搞懂意思。之前本想用排列组合的，但是无果。然后用穷举的方法，做事做出来了，然而只得了三十分，测试的数据范围太大了

网上别人讲的是动态规划，没太明白他的意思，也一起贴出来。

import java.util.Scanner;

public class K好数 {
	
	static int k,l;
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		
		while(sc.hasNext()){
			k=sc.nextInt();
			l=sc.nextInt();
			
			//穷举的范围
			int min=(int)Math.pow(k,l-1);
			int max=(int)Math.pow(k,l);
			
			int count=0;
			for (int i = min; i < max; i++) {
				boolean fa=getbool(i);
				if(fa){
					count++;
					if(count==1000000007){
						count=0;
					}
				}
			}
			System.out.println(count);
		}
	}

	//转成进制
//	private static String getJZ(int i) {
//		String s="";
//		while(i!=0){
//			s=i%k+s;
//			i=i/k;
//		}
//		return s;
//	}
	
	//转成进制的优化
	private static boolean getbool(int i) {
		int a=i%k,b=0;
		i=i/k;
		while(i!=0){
			b=i%k;
			if(Math.abs(a-b)==1)
				return false;
			else
				a=b;
			i=i/k;
		}
		return true;
	}
}

别人写的动态规划的：

import java.util.*;
import java.math.*;
import java.util.regex.*;

public class Main {

    final static int MOD = 1000000007;
    final static int INF = 0x3f3f3f3f;
    final static int NUM = 100;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int k,l;
        int ans;
        while(sc.hasNext()) {
            k=sc.nextInt();l=sc.nextInt();
            ans=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++) {
                ans+=nums[l-1][j];
                ans%=MOD;
            }
            System.out.println(ans);
        }
    }
}

好难啊！！