Codeforces Round #549(div2) D.The Beatles(数学)
题意
给一个圆,圆上共有 nk个点,分别编号为 0~ nk−1,任意两个相邻的点距离 1km,其中在编号为 kt+1的点上有快餐店.
现在有一个人一开始在编号为 s的点,他每轮跑 l km,再次回到 s时停止跑.
由于某种神奇的因素,他忘记了 s和 l的值,但他知道一开始 s处距离最近的饭店的距离为 a km,跑了 l km后距离最近的饭店为 b km,先让你求最小的跑步轮次 x和最大的跑步轮次 y.
做法
可以列出下列方程组:
s=1±a(modk)
s+l=1±b(modk)
tl=0(modnk)
其中 t为满足方程的最小正整数解.
显然有 t=(l,nk)nk,而 l≡±a±b(modk),只有 4n种取值.枚举求 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;
}