一类类欧几里得问题的做法

这篇 blog 是瞎胡的,如果有错误请指出一下...

问题

给定非负整数 \(a\),正整数 \(k,p\) 和整数 \(l, r\)\(0 < k < p,-p < l \le r < p\)。(如果存在) 求出最小的大于等于 \(a\) 的整数 \(i\) 使得 \(ki\)\([l,r]\) 中的某个数模 \(p\) 同余。

做法

\(a\) 不为 \(0\) 时,我们可以设 \(i' = i - a\),求出最小的非负整数 \(i'\),可以转化为 \(a = 0\) 的情况。(也很容易使 \(l,r\) 仍然满足的 \(-p < l, r < p\))

原问题等价于寻找最小的非负整数 \(i\),使得非负整数 \(q\)\(ki - qp \in [l,r]\)。(这两个问题等价的条件是 \(l, r < p\),这就是要限制 \(l, r < p\) 的原因)

把给定非负整数 \(k, p\) 和整数 \(l\le r\) (这里我们不限制 \(l,r\) 的范围),求最小的非负整数 \(i\),使得存在非负整数 \(q\),满足 \(ki - qp \in [l,r]\) 这样的一个问题记为 \((k, p, l, r)\)

对于一个问题 \((k, p, l, r)\)。如果 \(r - l \ge p\),可以把 \(r\) 改为 \(l + p -1\),得到一个等价问题。

对于 \(r \ge p\) 的情况,\(l > 0\)\(ki \ge l\),所以 \(i \ge \lceil \frac l k \rceil\)。设 \(i' = i - \lceil \frac l k \rceil\),那么 \(i'\) 是问题 \((k, p, l - k\lceil \frac l k \rceil, r - k\lceil \frac l k \rceil)\) 的答案。这样就转化为了一个满足 \(l,r < p\) 的问题,下面我们只考虑这样的问题。

对于一个 \(l, r < p\) 的问题 \((k, p, l, r)\),它等价于求最小的 \(i\) 使得 \(ki\)\([l,r]\) 中某个数模 \(p\) 同余,所以我们可以把 \(k\) 改为 \(k \bmod p\)

如果 \(l \le -p\),我们可以同时把 \(l,r\) 增加 \(\lfloor \frac {-p-l} p \rfloor + 1\) 使得 \(-p < l, r < p\)

如果已经确定了 \(i\),合法的 \(q\) 只有一个。反过来,如果我们找到最小的非负整数 \(q\),那么 \(i \in [l + qp, r + qp]\),我们很容易直接算出最小的 \(i\)。所以我们把问题 \((k,p,l,r)\) 转化为了问题 \((p, k, -r, -l)\)

通过上面这几步转化,我们可以把任意一个问题 \((k,p,l,r)\) 转化为一个规模更小的问题。容易发现这是一个辗转相除的过程,复杂度为 \(\mathcal O ( \log p )\)

\(q\) 即是 \(\lfloor \frac {ki} p \rfloor\),所以我们也可以先求出最小的正整数 \(q\),使得存在正整数 \(i\) 使上式成立,然后再去利用 \(q\) 求出最小的 \(i\) (这时 \(ki \bmod p\) 是等差数列,所以就很容易了)。

\(l = 0\)\(l = 1\), \(r = p-1, 0 \le l \le r < p\) 是几种比较常见的特殊情况。

注意 long long。

代码

没跑过。可能是错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int solve(int k, int p, int l, int r) {
if (r >= l + p) r = l + p - 1;
if (r >= p) {
int x = (l + k - 1) / k;
int res = solve(k, p, l - k * x, r - k * x);
if (res == -1) return -1;
return x + res;
}
k %= p;
if (l <= -p) {
int x = ((- p - l) / p) + 1;
l += p * x, r += p * x;
}
if (!k) {
if (l <= 0 && r >= 0)
return 0;
else
return -1;
}
int q = solve(p, k, -r, -l);
if (q == -1) return -1;
// ki >= l + qp
return max(0ll, (l + 1LL * q * p + k - 1) / k);
}