[数据结构与算法]任意个数的最小公倍数 和的平方与平方的和之间的差值_Java每日练习题及题解（11月17日）

《Java每日练习题及题解》系列目录

1.有限条件求和_Java每日练习题及题解(11月15日)
2.最大质因数 最大回文数乘积 字符串String类用法_Java每日练习题及题解（11月16日）
3.任意个数的最小公倍数 和的平方与平方的和之间的差值_Java每日练习题及题解（11月17日）

题目一：最小公倍数

一、题干

2520是可以被从1到10所有自然数整除的最小的数，即为从1到10的自然数的最小公倍数，求从1到20所有自然数的最小公倍数。

二、输出样例

232792560

三、解题思路

首先确定所需数据类型，本题数据较大，考虑用long类型或者BigInterger类(可参考BigInterger类)来实现。
思路：从两个数最大公约数推出两个数的最小公倍数

解题前所需要知道的数学原理

求最大公约数

辗转相除法： gcd(a,b) = gcd(b,a mod b)。
假如，需要求 1997 和 615 两个正整数的最大公约数,用辗转相除法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

求最小公倍数

方法：求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
例如，求 [18，20]，即得 [18，20]=18×20÷（18，20）=18×20÷2=180。

所以！
求几个自然数的最小公倍数，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个为止。
最后所得的那个最小公倍数，就是所求的几个数的最小公倍数。

四、实现代码一（long类型）

//求最大公约数
    public static long gcd(long a,long b){
        return b==0?a:gcd(b,a%b);
    }
//求最小公倍数
    public static long lcm(long a,long b){
        return a*b/gcd(a,b);
    }
//主函数
    public static void main(String[] args) {
        long res=1L,i=1L;
        while(i<20){
            ++i;
            res=lcm(res,i);
        }
        System.out.println(res);
    }

五、实现代码二（采用BigInteger类）

public class p005 {
 private static BigInteger lcm(BigInteger x, BigInteger y) {
        return x.divide(x.gcd(y)).multiply(y);
    }
    public String run() {
        BigInteger allLcm = BigInteger.ONE;
        for (int i = 1; i <= 20; i++)
            allLcm = lcm(BigInteger.valueOf(i), allLcm);
        return allLcm.toString();
    }
    public static void main(String[] args) {
        System.out.println(new p005().run()); //232792560
    }
 }
 }

题目二：和的平方与平方的和之间的差值

一、题干

前十个自然数的平方的和为： 1²+2²+3²+?+10²=385
而前十个自然数和的平方为：(1+2+3+?+10)² =55 ²=3025
两者的差为3025?385=2640
求前一百个自然数的和的平方与平方的和之间的差值。

二、输出样例

25164150

三、解题思路

思路一：分别求平方和，和的平方。
思路二：推导公式

N 个数的和 sum1 = N(N + 1) / 2.
N 个数的平方和 sum2 = N(N + 1)(2N + 1) / 6
sum1² - sum2 = (N⁴ / 4) + (N³ / 6) - (N² / 4) - (N / 6)
= N(N?1)(N+1)(3N+2)/12

四、实现代码一

public class ex6 {
//求前n个自然数的平方的和
    public static long SumOfSquare(int n){
        long res=0;
        while(n>0){
            res+=n*n;
            n--;
        }
        return res;
    }
//求前n个自然数和的平方
    public static long SquareOfSum(int n){
        long res=0,sum=0;
        while(n>0){
            sum+=n;
            n--;
        }
        return sum*sum;
    }
    public static void main(String[] args) {
        int n=100;
        System.out.println(SquareOfSum(n)-SumOfSquare(n));
    }
}

五、实现代码二

public class p006 {
    private static final int N = 100;
    public String run() {
        int sum1 = 0; //和
        int sum2 = 0; //平方和
        for (int i = 1; i <= N; i++) {
            sum1 += i;
            sum2 += i * i;
        }
        return Integer.toString(sum1 * sum1 - sum2);
    }
    public String run2() {
// int s =(N*N*N*N / 4) + (N*N*N / 6) - (N*N / 4) - (N / 6);
        int s =N*(N-1)*(N+1)*(3*N+2)/12;
        return Integer.toString(s);
    }
    public static void main(String[] args) {
        System.out.println(new p006().run2()); //25164150
    } 
}