https://codeforces.com/contest/1143/problem/D
题意
有nk个城市,第1,k+1,2k+1,...,(n-1)k+1城市有餐厅,你每次能走l距离,a为起始位置离最近餐厅的距离,b为走了一次后离最近餐厅的距离,给出n,k,a,b,求你回到起点最少和最多停留次数
题解
- (yl=xnk,有y=xnk/l,即y=lcm(xnk,l)/l)
- 枚举a(两种情况),b(两种情况),维护最大,最小值
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,a,b,p,d,mx=-1e17,mi=1e17;
ll gcd(ll a,ll b){
if(b>a)swap(a,b);
if(b==0)return a;
else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
int main(){
cin>>n>>k>>a>>b;
for(ll i=0;i<n;i++){
p=b+i*k;
if(p>n*k)p-=k;
d=abs(p-a);
mi=min(lcm(n*k,d)/d,mi);
mx=max(lcm(n*k,d)/d,mx);
}
for(ll i=0;i<n;i++){
p=(k-b)+i*k;
if(p>n*k)p-=k;
d=abs(p-a);
mi=min(lcm(n*k,d)/d,mi);
mx=max(lcm(n*k,d)/d,mx);
}
a=k-a;
for(ll i=0;i<n;i++){
p=b+i*k;
if(p>n*k)p-=k;
d=abs(p-a);
mi=min(lcm(n*k,d)/d,mi);
mx=max(lcm(n*k,d)/d,mx);
}
for(ll i=0;i<n;i++){
p=(k-b)+i*k;
if(p>n*k)p-=k;
d=abs(p-a);
mi=min(lcm(n*k,d)/d,mi);
mx=max(lcm(n*k,d)/d,mx);
}
cout<<mi<<" "<<mx;
}