6246 풍선 놀이

최대공약수 그런걸로 구해볼까..? 싶었는데 시간복잡도 내로 돌아서 그냥 반복문 두 번 돌렸다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n, q;
    cin >> n >> q;

    vector<int> v(n + 5);
    for (int i = 0; i < q; i++)
    {
        int l, k;
        cin >> l >> k;

        for (int j = l; j <= n; j += k)
            v[j] = 1;
    }

    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (v[i] == 0)
            sum++;
    }
    cout << sum << endl;

    return 0;
}