PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: indreshsingh
Tester: udhav2003
Editorialist: iceknight1093
DIFFICULTY:
3058
PREREQUISITES:
PROBLEM:
Given N, partition the integers \{1, 2, \ldots, 2N\} into N pairs such that number of pairs (x, y) with \gcd(x, y) = 1 is minimum.
EXPLANATION:
First, let’s look at which pairs unavoidably must have \gcd = 1.
- \gcd(1, x) = 1 for any integer x, so the pair containing 1 is sad.
- If p is a prime number such that N+1 \leq p \leq 2N, then \gcd(p, x) = 1 for any other integer between 1 and 2N.
Every other number has either a factor or a multiple within the range [2, 2N], so there’s potential to form a non-coprime pair using it.
This immediately gives us a lower bound on the number of sad pairs: if there are k primes between N+1 and 2N, then there are at least \left \lceil \frac{k+1}{2} \right\rceil sad pairs; at best these primes and 1 can be paired with each other.
In fact, this lower bound is also tight!
We’ll prove this by construction.
Notice that if \gcd(x, y) \gt 1, there must exist a prime p that divides both x and y.
Of course, with respect to the problem we’re dealing with, p must also lie between 2 and N (since we’ve already seen that primes \gt N are coprime with everything else).
So, let p_1 \lt p_2 \lt \ldots \lt p_m be the distinct primes between 2 and N.
Then, we can do the following:
- Consider these primes in descending order, i.e, p_m down to p_1.
- For a fixed prime p_i,
- Let L_i denote the list of all multiples of p_i that haven’t yet been paired.
Note that L_i surely contains at least p_i and 2p_i; though it might contain more elements as well. - If L_i has even size, pair off all its elements within themselves; which is fine since any pair created this way will have a gcd that’s a multiple of p_i.
- If L_i has odd size, we need to discard one element and pair the rest.
Here, discard 2p_i and pair everything else up.
- Let L_i denote the list of all multiples of p_i that haven’t yet been paired.
At the end of this process, most elements have been paired up with some others to form \gcd \gt 1 pairs.
The only unpaired elements are the ones we discarded when L_i had odd size — however, note that we chose 2p_i each such time, i.e, all these elements are even!
So, we can pair them among themselves without issue.
Finally, we’re left with at most one unpaired element, along with 1 and all the primes from N+1 to 2N.
Pair them up arbitrarily since the gcd of any pair will be 1.
It’s not hard to see that this process creates exactly \left\lceil \frac{k+1}{2} \right\rceil pairs with \gcd = 1, since only the very last step creates such pairs.
Since that was our lower bound for sad pairs, and we’ve attained it, optimality is proved.
As for implementation, there are only two nontrivial parts here:
- Finding all primes upto 2N
- Finding the lists L_i, i.e, unpaired multiples of prime p_i.
The first part can be done in \mathcal{O}(N\log N) (or better, depending on implementation) using the sieve of Eratosthenes.
The second part can be done in a brute-force manner, since iterating across all multiples of p_i for each prime upto N has a time complexity of \mathcal{O}(N\log\log N) (and is very similar to the aforementioned sieve anyway).
TIME COMPLEXITY
\mathcal{O}(N\log N) per test case.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 2e5 + 5;
bool prime[N + 1];
int num_primef[N + 5];
void SieveOfEratosthenes() {
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= N; i += p)
prime[i] = false;
}
}
prime[1] = false;
}
void precompute() {
num_primef[1] = 0;
for (int i = 2; i <= N; i++) {
if (prime[i]) num_primef[i] = num_primef[i - 1] + 1;
else num_primef[i] = num_primef[i - 1];
}
}
void solve() {
int n;
cin >> n;
int cnt = num_primef[2 * n] - num_primef[n] + 1;
cout << cnt / 2 + cnt % 2 << '\n';
vector< int > s;
for (int i = 2; i <= n; i++) if(prime[i]) s.pb(i);
vector < int > even;
unordered_map < int, int > m;
int sz=s.size();
for (int k=sz-1;k>=0;k--) {
int num = s[k];
int c = 0, i;
for (int j = num; j <= 2 * n; j += num) {
if (m[j] == 0) c++;
}
if (c % 2 == 0) {
cout << num << " " << num * 2 << '\n';
m[num] = 1;
m[2 * num] = 1;
i = num * 3;
} else {
int stop;
for (int j = num * 3; j <= 2 * n; j += num) {
if (m[j] == 0) {
stop = j;
break;
}
}
cout << num << " " << stop << '\n';
m[stop] = 1;
m[num * 2] = 1;
even.pb(num * 2);
i = stop + num;
}
vector < int > v;
for (; i <= 2 * n; i += num) {
if (m[i] == 0) v.pb(i), m[i] = 1;
}
for (int j = 0; j + 1 < v.size(); j += 2)
cout << v[j] << " " << v[j + 1] << '\n';
}
for (int i = 0; i + 1 < even.size(); i += 2) {
cout << even[i] << " " << even[i + 1] << '\n';
}
vector < int > final;
if (even.size() % 2) final.pb(even[even.size() - 1]);
final.pb(1);
for (int i = n + 1; i <= 2 * n; i++)
if (prime[i]) final.pb(i);
for (int i = 0; i + 1 < final.size(); i += 2) {
cout << final[i] << " " << final[i + 1] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
SieveOfEratosthenes();
precompute();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Tester's code (C++)
#pragma GCC optimisation("O3")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM1
#define LMOD 1000000006LL
#define fi first
#define se second
typedef long double ld;
const ll MAX = 200100;
const ll MAX2 = MAX;
const ll large = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vector<int> maxp(MAX);
for(int i = 2; i < MAX; i++){
if(maxp[i] == 0){
for(int j = i; j < MAX; j += i) maxp[j] = i;
}
}
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<bool> take(2*n + 1);
vector<pair<int, int>> ans;
vector<int> gp{1};
int c = 1;
for(int i = n + 1; i <= 2*n; i++){
if(maxp[i] == i){
gp.push_back(i);
c++;
}
}
if(c%2 == 0){
for(int i = 0; i + 1 < c; i += 2){
ans.push_back({gp[i], gp[i + 1]});
take[gp[i]] = take[gp[i + 1]] = true;
}
}
else{
gp.push_back(2);
c++;
for(int i = 0; i + 1 < c; i += 2){
ans.push_back({gp[i], gp[i + 1]});
take[gp[i]] = take[gp[i + 1]] = true;
}
}
for(int i = n; i > 2; i--){
if(maxp[i] == i){
vector<int> v;
for(int j = i; j <= 2*n; j += i){
if(!take[j]) v.push_back(j);
}
int k = v.size();
if(k%2 == 0){
for(int i = 0; i < k; i += 2){
ans.push_back({v[i], v[i + 1]});
take[v[i]] = take[v[i + 1]] = true;
}
}
else{
assert(begin(v)[1] == 2*i);
v.erase(begin(v) + 1);
k -= 1;
for(int i = 0; i < k; i += 2){
ans.push_back({v[i], v[i + 1]});
take[v[i]] = take[v[i + 1]] = true;
}
}
}
}
vector<int> v;
for(int j = 1; j <= 2*n; j++){
if(!take[j]){
v.push_back(j);
}
}
// for(auto x: v) cout << x << ' ';
// cout << endl;
int k = v.size();
assert(k%2 == 0);
for(int i = 0; i < k; i += 2){
ans.push_back({v[i], v[i + 1]});
take[v[i]] = take[v[i + 1]] = true;
}
assert(count(all(take), true) == 2*n);
cout << c/2 << '\n';
for(auto x: ans) cout << x.fi << ' ' << x.se << '\n';
cout << '\n';
}
return 0;
}
Editorialist's code (Python)
maxn = 2*10**5 + 5
sieve = [0]*maxn
for i in range(2, maxn):
for j in range(2*i, maxn, i): sieve[j] = 1
for _ in range(int(input())):
n = int(input())
bad = [1]
for i in range(n+1, 2*n+1):
if sieve[i] == 0: bad.append(i)
print((len(bad)+1)//2)
while len(bad) >= 2:
print(bad[-1], bad[-2])
bad.pop()
bad.pop()
mark = [0]*(2*n+1)
unpaired = -1
for i in reversed(range(2, n+1)):
if sieve[i] == 1: continue
cur = []
for j in range(i, 2*n+1, i):
if mark[j] == 0:
cur.append(j)
mark[j] = 1
if len(cur)%2 == 1:
if unpaired == -1: unpaired = 2*i
else:
print(unpaired, 2*i)
unpaired = -1
cur.remove(2*i)
while cur:
print(cur[-1], cur[-2])
cur.pop()
cur.pop()
if unpaired != -1: print(unpaired, 1)