为啥 $O(n\sqrt n)$ 过不了 2e5

invisible_person @ 2023-01-11 18:28:22

by yz_by @ 2023-01-11 18:36:08

by sanaka87 @ 2023-01-11 18:37:38

@yz_by 1s不是2e8吗

by sanaka87 @ 2023-01-11 18:38:29

@invisible_person 单纯常数写大了（）

by invisible_person @ 2023-01-11 18:39:50

@sanaka87 不懂啊，哪来常数

void work() {
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read() - 1;
    for (int i = 1; i <= n; i++)
        b[i] = read() - 1;
    for (int i = 1; i <= n; i++)
        d[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] <= b[i]) {
            d[1]++;
            continue;
        }
        for (int l = 1, r; l <= a[i] && l <= b[i]; l = r + 1) {
            r = min(a[i] / (a[i] / l), b[i] / (b[i] / l));
            if (a[i] / l == b[i] / l)
                d[l]++, d[r + 1]--;
        }
        d[a[i] + 1]++;
    }
    tot = 0;
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
        if (d[i] == n)
            ans[++tot] = i;
    }
    printf("%lld\n", tot);
    for (int i = 1; i <= tot; i++)
        printf("%lld ", ans[i]);
    putchar('\n');
} 

by invisible_person @ 2023-01-11 18:41:28

而且他给了 2s

by HarunluoON @ 2023-01-11 18:41:54

@yz_by @sanaka87 CF 的机子 1\rm s 可以跑 1\rm e9 吧（如果常数不很大的话）（ ？

by yz_by @ 2023-01-11 18:42:29

哦，我踩到误区了...

by shyr @ 2023-01-11 19:01:51

1s 5e8+ 都行吧

by Celtic @ 2023-01-11 19:05:13

整除分块四倍常数吧

by Celtic @ 2023-01-11 19:05:27

而且还全是除法运算