自动搬运

查看原文

来自洛谷，原作者为

	zzx114514 给岁月以文明，而不是给文明以岁月

搬运于2025-08-24 22:46:24，当前版本为作者最后更新于2023-07-17 18:37:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意

一条道路上有 $n$ 棵树，间隔为 $x$，现在要将这些树重新移植，使它们之间的间隔为 $y$，求共有多少棵树能留在原地不动。

解题思路

由小学数学知识可知，除第一棵树以外，其余的不动树必定是原来间隔 $x$ 和现在间隔 $y$ 的公倍数，否则一定会被移动，只需求出小于原先栽树的长度的 $x$ 和 $y$ 的公倍数个数即可。

注意事项

此题坑点在于 $n$ 的范围为 $10^{18}$，$x$ 和 $y$ 的范围为 $10^9$，两者相乘求种树的总长必定会超出 long long 的范围，这时我们可以掏出神器：__int128，这样就不会见祖宗了。

代码

#include <bits/stdc++.h>
using namespace std;
int t;
__int128 n,x,y,l;
__int128 read()
{
	__int128 res=0;
	char c[1005];
	scanf("%s",c);
	for(int i=0;i<strlen(c);i++)
	{
		res*=10;
		res+=c[i]-'0';
	}
	return res;
}
void print(__int128 num)
{
	if(num>9) 
		print(num/10);
	putchar(num%10+'0');
}
//注意使用__int128必须使用快读快输，不能使用cin,cout或scanf,printf 
__int128 lcm(__int128 a,__int128 b)
{
	return a*b/__gcd(a,b);//求最小公倍数，其中__gcd(a,b)是自带函数，表示最大公因数，可以直接调用 
}
int main()
{
	cin>>t;
	while(t--)
	{
		n=read(),x=read(),y=read();
		l=(n-1)*x;//求原来种树总长度 
		print(l/lcm(x,y)+1);//注意求完小于l的公倍数后要加回开头的那棵树 
		puts("");//一种换行的方法 
	}
	return 0;//华丽的结尾 
}

本蒟蒻第一篇题解，如有不足之处请指出QWQ