6246번: 풍선 놀이

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


$O(nq)$

#include<cstdio>
int n, q, ck[10001], c;
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0, x, y; i < q; i++) {
        scanf("%d%d", &x, &y);
        for (int j = x; j <= n; j += y) c += !ck[j]++;
    }
    printf("%d", n - c);
    return 0;
}