首页 > 其他分享 >LG8443

LG8443

时间:2024-01-20 17:47:12浏览次数:24  
标签:le 正整数 相等 LG8443 include 互质

JROI 果然很良心,签到题终于可以用来签到了。

这道题一看数据范围 $1 \le l \le r \le 10^{18} $,就能知道肯定是数学题。遇到数学题不用急,我们一步步分析。

回忆小学学习的关于互质的一条性质:相邻的两个正整数互质。形式化地说,若 \(a\) 和 \(b\) 为两个相邻的正整数,则 \(\gcd(a,b)=1\)。然后,我们又不难想到,一段连续的正整数,设它们的长度为 \(len\),若 \(len \ge 2\),则这些数的最大公约数就是 \(1\)。

如果不知道为什么,可以看一下这个例子。设 \(a,b,c\) 为三个连续的正整数,其中 \(a<b<c\),则可得 \(\gcd(a,b)=1\) 和 \(\gcd(b,c)=1\)。显而易见,\(\gcd(a,b,c)=1\)。更多个数的证明方法同理。

所以这题的思路就呼之欲出了。先分别对 \(l\) 和 \(r\) 除以 \(x\),再判断两数是否相等,若相等,则可以说明中间的数也相等(因为从 \(l\) 到 \(r\) 有单调性);若不相等,则说明中间有两个及以上的数,根据上面的推理,可知答案即为 \(1\)。

代码实现如下:

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		long long l,r,x;
		cin>>l>>r>>x;
		l/=x;
		r/=x;
		if(l==r) cout<<l<<endl;
		else cout<<1<<endl;
	}
	return 0;
} 

标签:le,正整数,相等,LG8443,include,互质
From: https://www.cnblogs.com/-lilong-/p/17976817

相关文章