提高培优班D13T4题解

常规
,
1

题目id:15800

题意

给定一个数字 n ，询问下标最小的区间 [l,r] 使得 \operatorname{lcm}(l,l+1,\dots,r)=n 。

此处下标较小定义为

\begin{cases}r\lt r^{\prime},&l=l^{\prime}\\l \lt l^{\prime},& \text{otherwise.} \end{cases}

n \leq 10^{18},t \leq 10^4 。

Solution

考虑区间长度为 1 的情况，若 n 为奇数，则必然存在区间 [\frac{n-1}{2},\frac{n-1}{2}+1] 小于区间 [n,n] 使得要求成立。若 n 为偶数，则必然存在区间 [2,\frac{n}{2}] 小于区间 [n,n] 使得要求成立。故答案区间长度不可能为 $1$。

考虑区间长度为 2 的情况，显然地，$l$ 与 r 即 l+1 互质，故 \operatorname{lcm}(l,r)=l\times(l+1) 。可以证明，对于 n=k\times (k+1),k\in N ，答案区间必然为 [k,k+1] 。显然地，对于 $n \leq 10^{18},k\leq \sqrt{10^{18}}$，且单调递增，可以二分来找到答案。

考虑区间长度大于等于 3 的情况，发现对于极端数据 n 为 10^{18} 级别时，答案区间内的数不会超过 10^6 ，故对于 10^6 以下的左端点暴力枚举以及右端点，并使用 map 维护答案。

时间复杂度为 \mathcal{O}(T \log n) 再加上预处理大概是 \mathcal{O}(4 \times 10^6) 的巨大常数，可以通过本题。

code

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long res=0,flag=1;
	char ch=getchar();
	while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=getchar();
	while(isalnum(ch)) res=res*10+ch-'0',ch=getchar();
	return res*flag;
}
map<long long,pair<int,int> > ans;
long long gcd(long long a,long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
void init()
{
	for(int l=1;l<=1500000;l++)
	{
		long long tmp=1ll*l*(l+1);
		for(long long r=l+2; ;r++)
		{
			tmp/=gcd(tmp,r);
			if(tmp>1e18/r)
				break;
			tmp*=r;
			if(ans.count(tmp)==false)
				ans[tmp]=make_pair(l,r);
		}
	}
	return ;
}
void solve(long long k)
{
	long long left=1,right=1e9;
	while(left<=right)
	{
		long long mid=(left+right)>>1;
		if(mid*(mid+1)==k)
		{
			ans[k]=make_pair(mid,mid+1);
			return ;
		}
		else if(mid*(mid+1)>k)
			right=mid-1;
		else if(mid*(mid+1)<k)
			left=mid+1;
	}
	return ;
}
int main(int argc,const char *argv[])
{
	init();
	int T=read();
	while(T--)
	{
		long long n=read();
		if(ans.count(n)==true)
		{
			printf("%d %d\n",ans[n].first,ans[n].second);
			continue;
		}
		solve(n);
		if(ans.count(n)==true)
		{
			printf("%d %d\n",ans[n].first,ans[n].second);
			continue;
		}
		printf("NIE\n");
	}
	return 0;
}

写在最后

三年 OI 一场空，不开 long long 见祖宗

1 个赞