[CF 449C] Jzzhu and Apples

作法：

我一開始是考慮一個構造：從$2$開始枚舉質數，當枚舉到一個質數$p$時，考慮所有被他整除且還沒被用過的數，如果有偶數個就全部連完，如果有奇數個就想辦法留一個下來。但後來發現不管留哪個都不對，例如當$p=2$且$n=6$時必須留$6$，$n=10$時則必須留$10$。而如果質數枚舉是從$3$開始，把$2$放在最後一個，並且如果$p$的倍數裡有奇數個沒被用過，就把$2p$留下來，這樣就可以把所有有辦法被選的數都選到了。（沒辦法被選到的點有$1$和比$\frac{n}{2}$大的質數）

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
bool vis[maxn] ;
int di[maxn],p[maxn],pcnt ;
void prime()
{
    for(int i=2;i*i<maxn;i++) if(!vis[i])
        for(int j=i*i;j<maxn;j+=i) vis[j]=1 , di[j]=i ;
    for(int i=3;i<maxn;i++) if(!vis[i])
        p[++pcnt]=i ;
    p[++pcnt]=2 ;
}
 
struct P{int x,y;};
vector<P> ans ;
bool used[maxn] ;
main()
{
    prime() ;
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=pcnt;i++) if(2*p[i]<=n)
    {
        int cnt=0 ;
        for(int j=p[i];j<=n;j+=p[i]) if(!used[j]) cnt++ ;
        if(cnt%2) used[2*p[i]]=1 ;
        for(int j=p[i],last=-1;j<=n;j+=p[i]) if(!used[j])
        {
            used[j]=1 ;
            if(last==-1) last=j ;
            else ans.push_back((P){last,j}) , last=-1 ;
        }
        if(cnt%2) used[2*p[i]]=0 ;
    }
    printf("%d\n",ans.size()) ;
    for(auto i : ans) printf("%d %d\n",i.x,i.y) ;
}