题解：CF1142A The Beatles

· · 题解

很数学的一道题啊。

首先假如我们知道了 l 的值应该如何求对应的次数呢？

行驶的总距离应当是 lcm(n\cdot k,l)，那对应的次数自然应该是 \frac{lcm(n\cdot k,l)}{l}。利用恒等式 lcm(x,y)=\frac{x\cdot y}{\gcd(x,y)} 可简化为 \frac{n\cdot k}{\gcd(n\cdot k,l)}。

那接下来就是如何求 l 的问题了。

我一开始想这道题的时候是先忽略了快餐店的位置固定规律。事实上，假如所有快餐店的位置是 d_0,d_1,\cdots,d_{n-1}，那么出发的位置一定是 d_i\pm a，第一次停下的位置一定是 d_j\pm b，l=\mid d_i\pm a-d_j\pm b\mid。

但是我们知道，快餐店的位置是可以直接公式表达的对吧？根据题意显然有 d_i=i\cdot m。所以 l=\mid d_i\pm a-d_j\pm b\mid=\mid i\cdot m\pm a-j\cdot m\pm b\mid=\mid (i-j)m\pm a\pm b\mid 且满足 i\not=j。

所以事实上我们只要枚举 i-j 的值就可以得出所有 l 的可能的取值了。枚举的时间复杂度是 \Omicron(n) 的。不过还要加上一个求 \gcd 的时间复杂度。所以总的就是 \Omicron(n\log (n\cdot k))。

代码很整齐啊。

:::info[code]

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
long long n,m,a,b,w_max,w_min;
int main()
{
    scanf("%lld %lld %lld %lld",&n,&m,&a,&b);
    w_max=n*m/__gcd(n*m,n*m+a+b);
    w_min=n*m/__gcd(n*m,n*m+a+b);
    for(int i=1;i<=n;i++)
    {
        w_max=max(w_max,n*m/__gcd(n*m,i*m+a+b));
        w_min=min(w_min,n*m/__gcd(n*m,i*m+a+b));
        w_max=max(w_max,n*m/__gcd(n*m,abs(i*m-a+b)));
        w_min=min(w_min,n*m/__gcd(n*m,abs(i*m-a+b)));
        w_max=max(w_max,n*m/__gcd(n*m,abs(i*m+a-b)));
        w_min=min(w_min,n*m/__gcd(n*m,abs(i*m+a-b)));
        w_max=max(w_max,n*m/__gcd(n*m,abs(i*m-a-b)));
        w_min=min(w_min,n*m/__gcd(n*m,abs(i*m-a-b)));
    }
    printf("%lld %lld",w_min,w_max);
    return 0;
}

:::