CF1142A The Beatles

佚名 6年前 (2019-05-15) 随笔 1060人围观抢沙发百度已收录

思路：

令p表示步数，l表示步长。由于p是使(l * p) % (n * k) == 0的最小的p，所以p = (n * k) / gcd(n * k, l).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

设l = k * x + r，则由题意可知r有四种可能的取值，分别是(a + b) % k, ((-a + b) % k + k) % k, ((a - b) % k + k) % k, ((-a - b) % k + k) % k，枚举各种情况计算即可。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll INF = 0x3f3f3f3f3f3f3f3f;
 5 ll n, k;
 6 void solve(ll r, ll & minn, ll & maxn)
 7 {
 8     for (int x = r ? 0 : 1; k * x + r <= n * k; x++)
 9     {
10         ll ans = n * k / __gcd(n * k, k * x + r);
11         minn = min(minn, ans);
12         maxn = max(maxn, ans);
13     }
14 }
15 int main()
16 {
17     ll a, b;
18     while (cin >> n >> k >> a >> b)
19     {
20         ll minn = INF, maxn = 0;
21         solve((a + b) % k, minn, maxn);
22         solve(((-a + b) % k + k) % k, minn, maxn);
23         solve(((a - b) % k + k) % k, minn, maxn);
24         solve(((-a - b) % k + k) % k, minn, maxn);
25         cout << minn << " " << maxn << endl;
26     }
27     return 0;
28 }