Codeforces Round #549 (Div. 2) D 数学

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;
}