题目描述

  After solving the Basic Gcd Problem, ZYB gives you a more difficult one:
  Given an integer , find two subset and of such that: and ; let and , there exists two permutations and such that for each , .
  Please find two subsets with maximum value of .

输入描述

  There are multiple test cases. The first line of input contains an integer , indicating the number of test cases.
  For each test case, there is only one line containing an integer . It's guaranteed that the sum of of all test cases will not exceed .

输出描述

  For each test case, output an integer in the first line. In the next lines, each contains two integers and , denoting the -th element in subset and .
  If there are multiple solutions, you can output any of them.

示例1

输入

2
4
10

输出

1
2 4
4
3 9
5 10
8 2
4 6

分析

  题意描述较为复杂，不妨直接令 和 都为 的标准排列，那么问题转化为：在区间 中取出尽量多的正整数对 ，满足 ，且每个数字只能使用一次；将 放入序列 ， 放入序列 ，序列的长度为 ，，且 ，有 。
  显然，对于 之间的全体偶数，可以随意配对。所以我们暂且不考虑偶数，将偶数放到最后配对。
  先枚举除 以外所有不超过 的质数 ，对于 的质数 ，不存在与其配对的数，首先将其剔除。若质数 ，那么对于不大于 的 的倍数，可以组成集合 ；显然，若集合 中任意两个元素都不互质；若 为偶数，那么正好可以两两配对；若 为奇数，取出 中一个偶数暂时不用（事实上， 中一定会包含 ），将剩余元素两两配对。此时，一部分偶数已经配对，如 。
  最后，将剩下的还没配对的偶数两两配对。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第四场） Problem H
Date: 8/18/2020
Description: Number Theory, Construction
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=200009;
int _;
int prime[N>>1];//质数
bool notprime[N];
int tot;
bool used[N];//记录是否使用
vector<int>ans;//记录答案
void EulerSieve(int);//欧拉筛
int main(){
    EulerSieve(N-1);
    for(cin>>_;_;_--){
        int n;
        ans.clear();//清空
        scanf("%d",&n);
        fill(used,used+n+2,0);//初始化
        int i,j;
        for(i=2;i<=tot;i++){
            //枚举除2以外的质数
            if(2*prime[i]>n){
                //剪枝
                //不必再继续枚举更大的质数
                break;
            }
            vector<int>prepared;//质数的倍数
            for(j=prime[i];j<=n;j+=prime[i]){
                if(!used[j]){
                    //未使用的p的倍数作为备选
                    prepared.push_back(j);
                }
            }
            if(prepared.size()&1){
                //奇数个
                //去掉其中一个的偶数
                for(j=0;j<prepared.size();j++){
                    if(prepared[j]%2==0){
                        prepared.erase(prepared.begin()+j);
                        break;
                    }
                }
            }
            for(j=0;j<prepared.size();j+=2){
                //两两配对
                used[prepared[j]]=used[prepared[j+1]]=1;
                ans.push_back(prepared[j]);
                ans.push_back(prepared[j+1]);
            }
        }
        vector<int>even;//剩余未使用的偶数
        for(i=1;i<=n;i++){
            if(!used[i]&&i%2==0){
                even.push_back(i);
            }
        }
        for(i=0;i<even.size();i+=2){
            if(i==even.size()-1){
                //若剩余偶数数量为奇数个
                //会枚举到even.size()-1
                //需要break
                break;
            }
            used[even[i]]=used[even[i+1]]=1;
            ans.push_back(even[i]);
            ans.push_back(even[i+1]);
        }
        printf("%d\n",ans.size()>>1);
        for(i=0;i<ans.size();i+=2){
            //两两输出答案
            printf("%d %d\n",ans[i],ans[i+1]);
        }
    }
    return 0;
}
void EulerSieve(int n){
    int i,j;
    for(i=2;i<=n;i++){
        if(!notprime[i]){
            prime[++tot]=i;
        }
        for(j=1;j<=tot&&i*prime[j]<=n;j++){
            notprime[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        }
    }
}