Gcd 在此代码中如何工作？

Question

我尝试解决一个关于 hackerearth 的问题，但我无法解决它，所以我看到 editorial.They 只给出了代码，没有 explanation.Can 你解释了为什么在这里使用 gcd 背后的逻辑？

问题：

史酷比和他所有的朋友都聚在一起参加派对。有 N 个朋友在场。史酷比真的很高兴看到他所有的朋友都聚集在一个地方，并很高兴向他们打招呼。

N位好友坐成一圈，编号从0到N-1。 Scooby 最初坐在 Ath 朋友旁边。跟一位朋友打过招呼后，顺时针走到第 B 位朋友身边，坐在他旁边打招呼。他重复这个直到他 returns 给 Ath 朋友。

史酷比兴奋不已，可能错过了跟朋友打招呼的机会。你的任务是找出 Scooby 在联系 A 之前会问候的朋友（包括 A）的数量。

给出的解决方案：

int main()
{
int T;
cin>>T;
while(T--)
{
    long long N,A,B;
    cin>>A>>B>>N;
    long long g=gcd(B,N);
    cout<<N/g<<endl;     
    }
return 0;
}

Answer 1

为了解释上述问题的解决方案，我将首先证明答案是 - LCM(B,N)/B 然后告诉你这是如何等于 N/GCD(B,N).

第一部分-
现在假设当他按照上述步骤再次到达 A 时，他会问候 f 个朋友。（注意，通过上述步骤问候的两个朋友不能相同）。此外，假设当他到达 A 时，他会转 r 圈。
现在我们可以说—— f * B = r * N = C.
让它等于某个常数 C。显然 C 是 B 和 N 的倍数，而且是 B 和 N 的最小公倍数（LCM）（因为我们想尽快给出答案这是第一次到达）。
所以f = LCM(B,N)/B。注意f是他打招呼的朋友数所以是必填项

第二部分-
对于两个正整数 a 和 b，它们的 GCD 和 LCM 分别为 g 和 l，我们有以下关系 - a*b = g*l.
从上面的关系我们可以说 -
LCM(B,N)*GCD(B,N) = B*N
=> LCM(B,N)/B = N/GCD(B,N)

所以我们终于有了答案 = LCM(B,N)/B = N/GCD(B,N).

Gcd 在此代码中如何工作？

How Gcd works in this code?

c++

greatest-common-divisor