2020牛客多校第四场H

题意：

在{1，2，3，...，n}中找到两个没有交集的序列使得gcd(ai, bi)>1，即找到ai和bi两两配对，使得他们不互质

思路：

显而易见，> n/2的素数是不能配对的。我们可以先把1～n的素数筛出来，从大到小枚举每个素数p（从小到大会漏）。

对于每个素数p，2p，3p，...... ，kp (k == n / p)两两配对，如果k为奇数，则把2p留下。

最后把留下的偶数两两配对，得到最终答案。

Code:

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <map>
#include <set>
#include <array>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define Time (double)clock() / CLOCKS_PER_SEC

#define sd(a) scanf("%d", &a)
#define sdd(a, b) scanf("%d%d", &a, &b)
#define slld(a) scanf("%lld", &a)
#define slldd(a, b) scanf("%lld%lld", &a, &b)

const int N = 2e5 + 10;
const ll M = 4e12;
const int mod = 1e9 + 7;

int t;
int n, cnt;
int primes[N];
bool st[N], vis[N];
vector<pair<int, int>> v;


void get(int n)
{
    cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("/home/jungu/code/in.txt", "r", stdin);
    // freopen("/home/jungu/code/out.txt", "w", stdout);
#endif
    // ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    sd(t);
    get(N - 10);
    while (t--)
    {
        sd(n);

        for (int i = 1; i <= n; i++)
        {
            vis[i] = false;
        }
        v.clear();

        int num = -1, a, b;
        for (int i = n / 2; i >= 2; i--)
        {
            if(st[i]) continue;

            if(i > n / 2) continue;
            int k = n / i * i;  

            for( ; k >= 0; k -= i){
                while(vis[k] && k >= 0){
                    k -= i;
                }
                if(k == 0){
                    break;
                }
                vis[k] = true;
                a = k;
                while(vis[k] && k >= 0){
                    k -= i;
                }
                if(k == 0){
                    break;
                }
                vis[k] = true;
                if(k == 2 * i){
                    if(num == -1){
                        num = k;
                    }
                    else{
                        v.push_back({k, num});
                        num = -1;
                    }
                    k -= i;
                    vis[k] = true;
                }
                v.push_back({a, k});

            }
            
        }
        printf("%d
", (int)v.size());
        for(auto x : v){
            printf("%d %d
", x.first, x.second);
        }
    }

    return 0;
}