算法训练最大最小公倍数

2019-11-14 09:48:48

字体：大中小

来源：转载

供稿：网友

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

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

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

（PS:下面是我的代码。）

package 最大最小公倍数;import java.math.BigInteger;import java.util.Scanner;public class Main { public static BigInteger GCD(BigInteger a , BigInteger b){ BigInteger gcd ; while( !b.equals(BigInteger.ZERO)){ gcd = a.remainder(b); a = b; b = gcd; } gcd = a; return gcd; } public static BigInteger Max_GCM(BigInteger n){ int cnt = 0; BigInteger mul = n; BigInteger j = n.subtract(BigInteger.ONE); while(cnt != 2){ if ( GCD(mul,j).equals(BigInteger.ONE)){ mul = mul.multiply(j); cnt++; } j = j.subtract(BigInteger.ONE); } return mul; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); String str = in.next(); BigInteger n = new BigInteger(str); BigInteger TWO = new BigInteger("2"); if ( n.compareTo(TWO) == 0){ System.out.PRint(2); }else if ( n.compareTo(BigInteger.ONE) == 0){ System.out.print(1); }else if ( n.compareTo(BigInteger.ZERO) <= 0){ System.out.print(0); }else{ BigInteger max = Max_GCM(n); System.out.print(max); } in.close(); }}

（PS：百度了下，由于后台测试数据出问题，所以判的只有60分） 这里写图片描述 (PS:下面是网上的AC代码，和自己相比，自己简直low到家了。数学结论不知道，真心不知道那些参加ACM的同学是怎么挺过来的。。。)

#include<iostream>using namespace std;int main(){ long long n,ans; cin>>n; if(n<=2) ans=n; else if(n%2==1) ans=n*(n-1)*(n-2); else { if(n%3==0) ans=(n-1)*(n-2)*(n-3); else ans=n*(n-1)*(n-3); } cout<<ans<<endl; return 0;}

上一篇：【bzoj3620】似乎在梦中见过的样子

下一篇：函数与数组