PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: TheScrasse
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh
DIFFICULTY:
2566
PREREQUISITES:
Basic Number theory
PROBLEM:
You are given two integers N and K.
Construct an array A_1, A_2, \dots, A_n consisting of distinct positive integers. The following conditions should be met:
- 1 \leq A_i \leq 2 \cdot 10^4;
- there isn’t any subset of A with sum K.
We can show that the answer always exists.
EXPLANATION:
Consider an integer d that does not divide K and take the first N multiples of d. It is obvious that no subset has a sum equal to K( the sum of each subset is divisible by d which does not divide K). The constraints on K allow us to find such d\leq 19 (2*3*5*7*11*13*17*19>10^6). Thus, iterate from d= 2\: to\: 19 and if d does not divide K take the first N multiples of d.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n >> k;
for (i = 1;; i++) {
if (k % i != 0) {
for (j = 1; j <= n; j++) cout << i * j << ' ';
cout << nl;
break;
}
}
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, k;
cin >> n >> k;
int d = 1;
while (d++)
if (k % d)
break;
for (int i = 1; i <= n; i++)
cout << i * d << ' ';
cout << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}