CF1142A The Beatles 乱搞

Description

---

有n*k个城市排成一个环，其中第1，k+1，2k+1…个城市是关键点
现在有个人从s出发，每次走l步后停下。已知这个人从s出发后走了x步又回到了s，且s与其最近关键点的距离恰好为a，第一次停下的位置与其最近关键点距离恰好为b，问可能的最小的x和最大的x
$n,k\le 10^5$

Solution

---

开了div1的vp只会A和B，瑟瑟发抖

考虑暴力怎么做，我们枚举s和l，看s是否符合a，s+l是否符合b，然后用$\frac{nk}{\gcd (l,nk)}$更新答案l
瞎分析一波可以发现我们调整一下枚举的范围就能做到十分优秀的线性复杂度
然后直接做就能过了。。记得开LL

Code

---

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (LL i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

typedef long long LL;
const LL INF=1e18;
const int N=200005;

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

LL gcd(LL x,LL y) {
	return !y?x:gcd(y,x%y);
}

int main(void) {
	LL n,m; scanf("%lld%lld",&n,&m);
	LL a,b; scanf("%lld%lld",&a,&b);
	LL mn=INF,mx=0,l1=b-a,l2=m-b-a;
	if (l1<0) l1+=m;
	if (l2<0) l2+=m;
	rep(s,1,m+1) {
		if (std:: min(s-1,m+1-s)!=a) continue;
		rep(l,1,m) {
			LL x=(s+l-1)%(n*m)+1;
			if (std:: min((x-1)%m,m-(x-1)%m)!=b) continue;
			for (LL w=l;w<=n*m;w+=m) {
				LL x=(s+w-1)%(n*m)+1;
				LL tmp=n*m/gcd(w,n*m);
				mn=std:: min(mn,tmp);
				mx=std:: max(mx,tmp);
			}
		}
	}
	printf("%lld %lld\n", mn,mx);
	return 0;
}