3711번: 학번

https://www.acmicpc.net/problem/3711


$O(na)$

m값을 올리면서 모두 다른지 체크한다.

#include<cstdio>
int main() {
    int n;
    for (scanf("%d", &n); n; n--) {
        int g, a[300], ck[1000000] = { 0, };
        scanf("%d", &g);
        for (int i = 0; i < g; i++) scanf("%d", a + i);
        for (int i = 1;; i++) {
            int j = 0;
            for (; j < g&&ck[a[j] % i] ^ i; j++) ck[a[j] % i] = i;
            if (j == g) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}

$O(ng^2\sqrt a)$

임의의 두 정수 x, y에 대해 abs(x-y)의 약수는 답이 될 수 없으므로 제외한다.

#include<cstdio>
#include<cstdlib>
int n;
int main() {
    for (scanf("%d", &n); n--;) {
        int g, a[300], i, j, k, x, ck[1000000] = { 0, };
        scanf("%d", &g);
        for (i = 0; i < g; i++) scanf("%d", a + i);
        for (i = 0; i < g; i++) for (j = i + 1; j < g; j++)
            for (k = 1, x = abs(a[i] - a[j]); k*k <= x; k++) if (x%k == 0) ck[k] = ck[x / k] = 1;
        for (i = 0; ck[++i];);
        printf("%d\n", i);
    }
    return 0;
}