一个错误的二分查找最小公倍数的代码
作者:
Soel
,
2022-12-05 20:16:09
,
所有人可见
,
阅读 159
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
/*题目要求,读入n个数字,要求求出这n个数字的最小公倍数
input:
输入n,n为数字个数,接下来有n个数字读入;
output:
输出一个结果,结果为最小公倍数;
*/
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n;
int l, r;//定义左右边界
int s;
bool check(int mid_c) { //判断性质
for (int i = N - n; i <= N - 1;i++) {
if (mid_c % q[i]) {
s = mid_c;
return true;
}
}
return false;
}
int main() {
//输入需要计算最小公倍数数组的个数,按照空格隔开
scanf("%d", &n);
for (int i = 0; i < n;i++) scanf("%d", &q[i]); //读入n个数组
for (int i = 0; i < n;i++) r *= q[i]; //右边界显然为n个数组的数值乘积
sort(q, q + N); //排序找到最大值,显然最大值为左边界
l = q[N-1];
for (int i = 0; i < 10000;i++) {//暴力二分一万次
int mid = l+r>>1;//确定二分的中点
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", r);
return 0;
}