Codeforces Round #549(div2) D.The Beatles(数学)

题意

给一个圆，圆上共有 n k ​ nk​ nk​个点，分别编号为 0 ​ 0​ 0​~ n k − 1 ​ nk-1​ nk−1​,任意两个相邻的点距离 1 k m ​ 1km​ 1km​,其中在编号为 k t + 1 ​ kt+1​ kt+1​的点上有快餐店.

现在有一个人一开始在编号为 s ​ s​ s​的点,他每轮跑 l ​ l​ l​ k m km km​,再次回到 s ​ s​ s​时停止跑.

由于某种神奇的因素，他忘记了 s ​ s​ s​和 l ​ l​ l​的值，但他知道一开始 s ​ s​ s​处距离最近的饭店的距离为 a ​ a​ a​ k m km km,跑了 l ​ l​ l​ k m km km后距离最近的饭店为 b ​ b​ b​ k m km km,先让你求最小的跑步轮次 x ​ x​ x​和最大的跑步轮次 y ​ y​ y​.

做法

可以列出下列方程组:

s = 1 ± a ( m o d k ) ​ s = 1 \pm a \pmod k ​ s=1±a(modk)​

s + l = 1 ± b ( m o d k ) ​ s + l = 1 \pm b \pmod k ​ s+l=1±b(modk)​

t l = 0 ( m o d n k ) ​ t l = 0 \pmod {nk}​ tl=0(modnk)​

其中 t ​ t​ t​为满足方程的最小正整数解.

显然有 t = n k ( l , n k ) ​ t = \frac{nk}{(l,nk)}​ t=(l,nk)nk​​,而 l ≡ ± a ± b ( m o d k ) ​ l \equiv \pm a \pm b \pmod k​ l≡±a±b(modk)​,只有 4 n ​ 4n​ 4n​种取值.枚举求 g c d ​ gcd​ gcd​即可.

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
const int N = 1e3 + 7;
const ll mod = 1e9 + 7;


int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    ll n, k, a, b;
    cin >> n >> k >> a >> b;
    ll temp = n * k, t[4] = {a + b, a - b, b - a, -a - b};
    ll mx = LLONG_MIN, mi = LLONG_MAX;
    for(int i = 0; i < 4; i++) {
        ll tt = t[i];
        for(int j = 0; j < n; j++, tt += k) {
            mx = max(mx, abs(__gcd(tt, temp)));
            mi = min(mi, abs(__gcd(tt, temp)));
        }
    }
    cout << temp / mx << ' ' << temp / mi << endl;
    return 0;
}