题意
给定一个整数 \(M\),求是否存在一个区间 \([a,b]\) 使得 \(M\) 为 \([a,b]\) 这个区间中所有数的最小公倍数。
解题方法
1. 区间长度 \(= 2\)。
二分查找 \(a\),由于相邻的两个数互质, \(lcm[a,b]\) 等于 \(a(a + 1)\)。
2. 区间长度 \(> 2\)
此时,发现 \(a\) 和 \(b\) 都不是很大,\(a\) 最大不超过 \(1.5 \times 10^6\),可以接受直接预处理的时间复杂度。
因此,我们枚举左端点 \(a\),向右进行累乘,直到最小公倍数大于 \(10^{18}\)。
可以用 map 进行左右端点的映射。
代码实现
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
int n;
long long m;
map<long long, pair<int, int> > M;
long long gcd(long long x, long long y)
{
return y ? gcd(y, x % y) : x;
}
void init()
{
for (long long l = 1; l <= 1500000; l ++)
{
long long res = (long long)(l * (l + 1));
for (int r = l + 2; ; r ++)
{
res /= gcd(res, r);
if (res > inf / r) break;
res *= r;
if (!M.count(res)) M[res] = make_pair(l, r);
}
}
}
pair<int, int> search(long long x)
{
int l = 1, r = 1e9;
while (l <= r)
{
long long mid = l + r >> 1;
if (mid * (mid + 1) > x) r = mid - 1;
else if (mid * (mid + 1) < x) l = mid + 1;
else return make_pair(mid, mid + 1);
}
return make_pair(0, 0);
}
int main()
{
init();
scanf("%d", &n);
while (n --)
{
scanf("%lld", &m);
pair<int, int> ans = M[m];
if (ans.first)
{
printf("%d %d\n", ans.first, ans.second);
continue;
}
ans = search(m);
if (ans.first) printf("%d %d\n", ans.first, ans.second);
else puts("NIE");
}
}
标签:wielokrotno,return,题解,P6659,mid,long,ans,pair,first
From: https://www.cnblogs.com/tongyuxin/p/17157559.html