题解：B3744 [语言月赛202304] 移植柳树

Just_A_Sentence · 2024-11-09 11:28:08 · 题解

由题意易得，所有被保留的柳树一定满足离起点的距离是 \operatorname{lcm}(x,y) 的倍数。因此，我们可以直接计算有多少树可以被保留。

首先，一共有 (n-1)\times x 的距离上是有树的。而在这段距离上每隔 \operatorname{lcm}(x,y) 的距离就有一棵树被保留，这样我们就可以算出有多少个间距两端的树可以被保留。最后，由于我们算出的是间隔数，所以答案还要 +1。

答案为 (n-1)\times \operatorname{gcd}(x,y)/y+1。

（温馨提示：记得开 long long）

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    printf("%lld",(a-1)*__gcd(b,c)/c+1);
    return 0;
}