[POI 2014] Solor Panels

求Smin≤x≤Smax, Wmin≤y≤Wmax时gcd(x,y)的最大值. n组数据. (1≤n≤1000, 1≤Smin≤Smax≤10^9, 1≤Wmin≤Wmax≤10^9) gcd的最大值即这些数所有因子的最大值. 枚举因子d, d是内某数的因子当且仅当 同时内所有整数也是因子.

地枚举因子, 分别把这些线段取出来, 排序, 取并, 再做个two-pointer把两者求交.

担心时间会爆掉. 而且不开O2的运行时间是开O2的6倍......还是AC了, 经过对比, 跑得不算慢. 可是大家的代码怎么这么短......

只有种取值, 见[51nod 1225] 余数之和.

如果某段数的分别相等, 把它们放到一起考虑. 因为只需要比一下大小就知道这个区间是否合法, 而且求的是最大值, 所以这一段取右端点即可.

代码变短了, 可是跑的变慢了. rank 1的tangjz的代码又短又快, 就去唐老师的github代码库学习了一下. 原来倒着枚举就好.

跑得还是没有唐老师快......

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int s1, s2, w1, w2;
        scanf("%d%d%d%d", &s1, &s2, &w1, &w2);
        --s1, --w1;
        int i = min(s2, w2);
        while (true) {
            if (s1/i < s2/i && w1/i < w2/i) {
                printf("%d\n", i);
                break;
            }
            i = max(s2/(s2/i + 1), w2/(w2/i + 1));
        }
    }
    return 0;
}

原来的代码:

typedef pair<int, int> Seg;
const int N = 63250, inf = 1e9 + 1;
Seg s[N], w[N], t[N];
int ns, nw;

void cal(int st, int ed, Seg* v, int &n)
{
	int m = 0, l, r;
	for (int d = 1; d*d <= ed; ++d) {
		l = (st+d-1)/d;
		r = ed/d;
		if (l <= r) {
			if (d < l || d > r)
				t[m++] = Seg(d, d);
			t[m++] = Seg(l, r);
		}
	}

	sort(t, t+m);
	t[m++] = Seg(inf, inf);
	
	l = t[0].first;
	r = t[0].second;
	n = 0;
	Rep (i, 1, m) {
		if (t[i].first > r) {
			v[n++] = Seg(l, r);
			l = t[i].first;
			r = t[i].second;
		} else
			r = max(r, t[i].second);
	}
}

int main()
{
	int n, s1, s2, w1, w2;
	scanf("%d", &n);
	while (n--) {
		scanf("%d%d%d%d", &s1, &s2, &w1, &w2);
		cal(s1, s2, s, ns);
		cal(w1, w2, w, nw);
		int ans = 1, i = 0, j = 0;
		while (i < ns) {
			while (j < nw && w[j].first <= s[i].second) {
				if (w[j].second >= s[i].first)
					ans = max(ans, min(s[i].second, w[j].second));
				++j;
			}
			--j;
			++i;
		}
		printf("%d\n", ans);
	}
	return 0;
}

POI果然非常喵.