[Baekjoon] 백준 17173 배수들의 합 C++

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

17173번: 배수들의 합

 

문제

신원이는 백준에서 배수에 관한 문제를 풀다가 감명을 받아 새로운 문제를 만들어보았다. 자연수 N과 M개의 자연수 Ki가 주어진다. Ki중 적어도 하나의 배수이면서 1 이상 N 이하인 수의 합을 구하여라.

입력

첫 번째 줄에 N과 M가 주어진다. (2 ≤ N ≤ 1000, 1 ≤ M < N)

그다음 줄에 M개의 정수 Ki가 주어진다. (2 ≤ Ki ≤ 1000)

동일한 Ki는 주어지지 않으며, 오름차순으로 정렬되어있다.

출력

배수들의 합을 출력한다.

예제 입력 1

10 2
2 3

예제 출력 1

42

예제 입력 2 

1000 3
3 5 7

예제 출력 2

272066

 

코드

using namespace std;
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cmath>
#include <map>
#include <set>
#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321
#define ll long long
typedef pair<int, int> PII;
 
 
int arr[1001];
 
int main() {
    
    int sum = 0;
    int n, m;
    cin >> n >> m;
 
    while (m--) {
        int num;
        cin >> num;
 
        for (int i = num; i <= n; i += num) {
            arr[i] = 1;
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (arr[i]) sum += i;
    }
 
    cout << sum << "\n";
 
    return 0;
}