REMOVEMUL - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: suchit_07
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

1315

PREREQUISITES:

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}.

So, the answer is:

\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))
2

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?

3

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

4

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;