「EOJ 317A」击鼓传花（类欧）

题目链接

稍加转化的题意：给定 (a)，(b)，(l)，(r)，求最小非负整数 (x) 满足 (ax mod b in [l, r])。

思路：

首先可以把 (a) 变为 (a mod b)，不影响答案。现在只要支持把 (a)，(b) 的地位互换，我们就能像类欧一样搞了。

假设 (a eq 0)。考虑找一些平凡情况先判掉：若 (lceilfrac{l}{a} ceil le lfloorfrac{r}{a} floor)，(x_{min} = lceilfrac{l}{a} ceil)。如果不是这种情况，因为 (l le r)，就有 (lceil frac{l}{a} ceil = lfloor frac{r}{a} floor + 1)，因此一定存在 (M) 使 (a(M - 1) < l le r < aM)。

有了此性质，我们对式子 (l le ax - by le r) 变形：

[egin{split} & Leftrightarrow qquad l - ax ; & le -by & le r - ax \ & Leftrightarrow qquad ax - r ; & le by & le ax - l end{split} ]

记 (l' = (-r) mod a)，(r' = (-l) mod a)（都取非负）。上式也就是 (by mod a in [l', r'])。又因为 (y) 最小时 (x) 一定最小，所以通过 (b)，(a)，(l')，(r') 的问题得到 (y_{min}) 后就能推出相应的 (x_{min})。

发现根本没用到性质？其实用到了：根据式子推出 (l' = aM - r)，(r' = aM - l)，因此 (l' le r')。若没这个性质就可能 (l' > r')，新问题变成 (by mod a in [l', a - 1] cup [0, r'])，要分出两个子问题，复杂度就错了。

这样我们就通过了本题，时间复杂度 (O(log a))。

代码：

#include <bits/stdc++.h>

#define rep(i, p, q) for (int i = int(p); i <= int(q); i++)
#define per(i, p, q) for (int i = int(p); i >= int(q); i--)

using namespace std;

typedef long long ll;

const int inf = 2e9;

inline void put(int res) {
	printf("%d
", res == inf ? -1 : res);
}

int F(int a, int b, int l, int r) {
	a %= b;
	if (!l) return 0;
	if (!a) return inf;
	int M = (l - 1) / a + 1;
	if (a * M <= r) return M;
	int y = F(b, a, a * M - r, a * M - l);
	if (y == inf) return inf;
	return (l - 1 + ll(b) * y) / a + 1;
}

int T, a, b, s, l, r;

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d %d", &a, &b, &s, &l, &r);
		l = (l - s + b) % b;
		r = (r + 1 - s + b) % b;
		if (l < r) {
			put(F(a, b, l, r - 1));
		} else {
			put(min(F(a, b, l, b - 1), r ? F(a, b, 0, r - 1) : inf));
		}
	}
	return 0;
}

评分：

思维难度：5/10

代码难度：1/10

评价：5/10