题意:
写出图片说明 的两个子集A,B,并且*两个子集的长度相等,且两个子集的交集为空,并且相对应位置的图片说明 *,然后第一行输出长度m,下来m行输出所构成的子集中的顺序
题解:
直接看样例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
7 14
5 15
3 6
9 12
2 4
8 10
如果要gcd>1那么对于每一个质数,所需要的数必须为他的倍数
那么对于每一个质数,比如上面出现的11和13无法利用,然后对于出现的7只有14可以利用
如果提前将14利用,即和2一起使用,那么对于最终的答案,必定剩下1个2的倍数和7,不符合题意
然后我们推广一下
如果存在质数x的倍数有偶数个,那么就可以完美匹配
然后对于每个质数x,比如2和7举例,2比7容易利用,那么我们先把7符合的剔除,下来再寻找2符合的
但是如果质数x的倍数存在奇数个,那么我们此时选择,x的倍数中第二小的
还是上面的意思,质数本身为第一小,那么此时不选,之后就没机会了,如果选的太大,那么之后也可能没有机会
举例3,6,9
然后要提前打个表,下来开始处理,答案不唯一,咋输出都行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0)

// *start on @date: 2020-07-20 15:05

const int N = 500010;
bool notprime[N];
int prime[N];
int pn;

int n;
bool vis[N];
vector<pair<ll, ll> > ans;
void GetPrime()
{
    pn = 0;
    notprime[1] = 1;
    int i;
    for (i = 2; i < N; i++)
    {
        if (notprime[i] == false)
            prime[pn++] = i;
        for (int j = 0; j < pn && prime[j] * i < N; j++)
        {
            notprime[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int main()
{
    GetPrime();
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        ans.clear();
        for (int i = 2; i <= n; i++)
            vis[i] = 0;
        for (int i = n; i >= 2; i--)
        {
            if (notprime[i] == true)
                continue;
            int pri_now = i;
            int max_time = (n / i) * i;
            for (int j = max_time; j > i; j = j - i)
            {
                if (vis[j])
                    continue;
                if (pri_now == -1)
                    pri_now = j;
                else
                {
                    ans.push_back(make_pair(pri_now, j));
                    vis[pri_now] = 1;
                    vis[j] = 1;
                    pri_now = -1;
                }
            }
        }
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i].first << " " << ans[i].second << '\n';
    }
    return 0;
}