1419 最小公倍数挑战
- 1 秒
- 131,072 KB
- 40 分
- 4 级题
几天以前，我学习了最小公倍数。玩得挺久了，想换换口味。
我不想用太多的数字，我想从1到n中选三个数字（可以相同）。使得他们的最小公倍数最大。
收起
输入
单组测试数据。 第一行有一个整数n (1≤n≤1,000,000)。
输出
输出一个整数表示选三个数字的最大的最小公倍数。
输入样例
9 7
输出样例
504 210
很简单，特判n <= 3，然后取后四个数 ， 暴力跑一下，注意求ICM的时候，先/gcd，不然乘法会爆ll
例如：296604
代码如下：
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se secondusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
//inline int sign(db a) { return a < -eps ? -1 : a > eps;}
//inline int cmp(db a,db b){ return sign(a - b);}
//ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
//ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
//int fa[maxn];
//int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
ll c,n,k;
int main() {ios::sync_with_stdio(false);while(cin >> n) {if(n == 1) {cout << 1 << endl;continue;}if(n == 2) {cout << 2 << endl;continue;}if(n == 3) {cout << 6 << endl;continue;}vector<ll>ans;ans.push_back(n);ans.push_back(n - 1);ans.push_back(n - 2);ans.push_back(n - 3);ll anss = 0;for(int i = 0;i < ans.size();i++){for(int j= i + 1;j < ans.size();j++){for(int k = j +1;k < ans.size();k++){ll num1 = ans[i] / __gcd(ans[i],ans[j]) * ans[j];ll num2 = ans[i] / __gcd(ans[i],ans[k])* ans[k];ll num = num1 / __gcd(num1,num2)* num2 ; anss = max(anss,num);}}}cout <<anss << endl;}
// cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}