-
题意：有间隔为k的n个点在数轴上，下标为 \(1，k+1, 2*k+1,\cdots (n-1)*k+1\) 首尾相接。设起点为s，步长为L，而现在只知道s距离最近的点的距离为a，和(s+L)距离最近的点的距离为b。问从s出发，第一次回到s走的最多和最少的步数。
-
分析：设走x步回到起点，那么有\(x*l = t * n * k\) 即走了x步饶了 t 圈
又因为x和t互质，即保证是第一次回到s，所以有 \(x = {n * k \over gcd(n*k, l)}\) 。所以枚举所有可能的 l ，得到gcd的最大值和最小值即可。
-
l (l<k时)的取值只有四种情况，画图即可得知
- \(l = k-a-b\)
- \(l = k+b-a\)
- \(l = a+b\)
- \(l = k+a-b\)
然后每一种情况又可以在原来的基础上多加 i 个k。总共4*n种 l
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a,b;
int main(){
cin>>n>>k>>a>>b;
ll mi = LONG_LONG_MAX;
ll mx = 0;
for(int i=0;i<n;i++){
ll x1 = __gcd(n*k,k-a-b + i*k);
ll x2 = __gcd(n*k,k+b-a + i*k);
ll x3 = __gcd(n*k,a+b + i*k);
ll x4 = __gcd(n*k,k+a-b + i*k);
mi = min(mi,min(x1,min(x2,min(x3,x4))));
mx = max(mx,max(x1,max(x2,max(x3,x4))));
}
cout<<(n*k)/mx<<' '<<(n*k)/mi<<endl;
return 0;
}
