Codeforces 449C - Jzzhu and Apples

Problem Statement:
449C - Jzzhu and Apples

Solution:
The approach to this problem is already very clear in the official editorial, this is mainly written for my self reference.

The strategy to solve this problem is through a constructive algorithm. Firstly we ignore all primes P bigger than \(\lfloor \frac{N}{2} \rfloor \) since those primes will not be able to matched. For all other P less than  \(\lfloor \frac{N}{2} \rfloor \), we iterate from the biggest prime down to the lowest prime:

1. If the total numbers divisible by P that has not been yet matched to any group equals to an even number, we can just match all of them exactly. Otherwise, if we have an odd number of such numbers, we throw away \(2P\) hence what remains will be even number of unmatched multiples of P, which we can then fully match.
2. In the end of the iteration, by the time we reach P = 2, all other multiple of other larger primes must have been matched, with possibly some unmatched 2P. Therefore all remaining unmatched numbers must be even, hence we can match as much as possible (i.e. match fully if there are even remaining numbers, or remove one if there are odd remaining numbers)

Why 2P is removed in 1? Because as such, we would not affect the next iteration, since 2P will not have any common factor with the rest of the multiple of the primes smaller than P but bigger than 2. Furthermore, 2P can still be used by the time we reach P=2, hence we know that we are not prematurely removing any numbers as the removed numbers can still be used for matching in the end.

Really great combinatorics thinking.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int N;
int mark[100003];
int vis[100003];
vector<pair<int,int> > ans;
int main(){
    for(int i=2;i*i<=100000;++i){
        if(mark[i])continue;
        for(int j=i;j*i<=100000;++j){
            mark[i*j]=1;
        }
    }
    scanf("%d",&N);
    for(int i=N/2;i>=2;--i){
        if(mark[i])continue;
        int cnt = 0;
        vector<int> st;
        for(int j=1;i*j<=N;++j){
            if(!vis[i*j]){
                ++cnt;
                st.push_back(i*j);
            }
        }
        if(cnt%2){
            st.erase(st.begin()+1);
        }
        for(int j=0;j<st.size();j+=2){
            ans.push_back(make_pair(st[j],st[j+1]));
            vis[st[j]] = 1;
            vis[st[j+1]] = 1;
        }
    }
    printf("%d\n",(int)ans.size());
    for(int i=0;i<ans.size();++i){
        printf("%d %d\n",ans[i].first,ans[i].second);
    }
    return 0;
}