P9213题解

zzx114514 · 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