# REMOVEMUL - Editorial

Author: suchit_07
Tester: tabr
Editorialist: iceknight1093

1315

None

# PROBLEM:

Starting with the set S = \{1, 2, \ldots, N\}, you’d like to reach its subset Q.
To do so, you can perform the following move:

• Choose an integer 1 \leq x \leq N, and delete the smallest multiple of x from S.
The cost of doing so is x.

Find the maximum cost required to turn S into Q.

# EXPLANATION:

Let D be the set of elements we need to delete - that is, D = \{1, 2, 3, \ldots, N\} \setminus Q.

For each x \in D, we need to choose a factor of it to delete it.
Given that our aim is to maximize the cost, obviously the best we can do is to choose x itself!

This means the answer is simply the sum of the elements of D.

Note that D has size N - M, and N can be quite large.
So, it’s not really possible to iterate across all the elements.

Instead, notice that D and Q together have all the elements \{1, 2, \ldots, N\}.
So, we know that

sum(D) + sum(Q) = 1 + 2 + \ldots + N \\ sum(D) = 1 + 2 + \ldots + N - sum(Q)

The elements of Q are given in the input, so computing their sum is easy.
Further, there’s the well-known formula 1 + 2 + \ldots + N = \frac{N\cdot (N+1)}{2}.

\frac{N\cdot (N+1)}{2} - \sum\limits_{i=1}^M Q_i

Note that the answer can exceed the range of 32-bit integers, so make sure to use larger datatypes such as long long (C++) or Long (Java).

# TIME COMPLEXITY

\mathcal{O}(M) per testcase.

# CODE:

Author's code (C++)
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
int T;
cin >> T;
while (T--) {
int N, M;
cin >> N >> M;
vector<int> Q(M);
long long s = 0;
for (int& i : Q)
cin >> i, s += i;
long long ans = (N * 1LL * (N + 1)) / 2;
ans -= s;
cout << ans << '\n';
}
return 0;
}


Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(n*(n+1)//2 - sum(a))


int n,k;
cin>>n>>k;
int a[k];
ll sum=0;
for(int i=0;i<k;i++){
cin>>a[i];
sum+=a[i];
}

cout << (n*(n+1))/2-(sum) << endl;


why this is showing wrong answers and not getting accepted?

chose long data type for n and k as well then try to submit.
I did it during contest and got submitted

write :
overflow is the reason, you may use 1LL in multiplication if you don’t want to use 64 bit integer:

cout << (1LL * n * (n + 1)) / 2 - sum << endl;