2020 우 객 여름 다 교 훈련소 (제4 회) - H

Harder Gcd Problem
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K Special Judge, 64bit IO Format:% lld
제목 설명
After solving the Basic Gcd Problem, ZYB gives you a more difficult one:
Given an integer n{n}n, find two subset A{A}A and B{B}B of {1,2,…,n}{1,2,\dots,n}{1,2,…,n} such that: ​∣A∣=∣B∣=m{​|A|=|B|=m}​∣A∣=∣B∣=m and A∩B=∅A \cap B = \emptysetA∩B=∅ Let A={a1,a2,…,am}A={a_1,a_2,\dots,a_{m}}A={a1​,a2​,…,am​} and B={b1,b2,…,bm}B={b_1,b_2,\dots,b_m}B={b1​,b2​,…,bm​}, there exists two permutations p1,p2,…,pmp_1,p_2,\dots,p_mp1​,p2​,…,pm​ and q1,q2,…,qmq_1,q_2,\dots,q_mq1​,q2​,…,qm​ such that for each 1≤i≤m1 \le i \le m1≤i≤m, gcd⁡(api,bqi)>1\gcd(a_{p_i}, b_{q_i}) > 1gcd(api​​,bqi​​)>1. Please find two subsets with maximum value of m{m}m.
입력 설명:
There are multiple test cases. The first line of input contains an integer T{T}T, indicating the number of test cases. For each test case, there is only one line containing an integer n{n}n (4≤n≤2×1054 \le n \le 2 \times 10^54≤n≤2×105) It’s guaranteed that the sum of n{n}n of all test cases will not exceed 2×1052 \times 10^52×105.
출력 설명:
For each test case, output an integer m{m}m in the first line. In the next m{m}m lines, each contains two integers aia_iai​ and bib_ibi​ (gcd⁡(ai,bi)>1\gcd(a_i, b_i) > 1gcd(ai​,bi​)>1), denoting the i{i}i-th element in subset A{A}A and B{B}B. If there are multiple solutions, you can output any of them.
예시 1
입력 복사 2 4 10 출력 복사 1 2 4 3 9 5 10 8 2 4 6
욕심 문 제 는 할 말 이 없다.

#include
using namespace std;
typedef long long ll;
const int N=1e6+500;
int f[N],vis[N],yz[N];
vector<int>q[N];
bool cmp(int x,int y) {
	if(yz[x]==yz[y])return f[x]>f[y];
	return yz[x]<yz[y];
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int n;
		scanf("%d",&n);
		for(int i=1; i<=n; ++i) {
			f[i]=0;
			vis[i]=0;
			yz[i]=0;
			q[i].clear();
		}
		for(int i=2; i<=n; ++i) {
			if(!f[i]) {
				for(int j=i; j<=n; j+=i) {
					if(!f[j])f[j]=i;
					yz[j]++;
					q[i].push_back(j);
				}
			}
		}
		int ans=0;
		vector<int>ans1;
		vector<int>ans2;
		for(int i=n/2; i>=2; --i) {
			sort(q[i].begin(),q[i].end(),cmp);
			int cut1=0,cut2=0;
			for(int j=0; j<q[i].size(); ++j) {
				if(!vis[q[i][j]]) {
					if(!cut1) {
						cut1=q[i][j];
					} else if(!cut2) {
						cut2=q[i][j];
					}
				}
				if(cut1&&cut2) {
					ans++;
					ans1.push_back(cut1);
					ans2.push_back(cut2);
					vis[cut1]++;
					vis[cut2]++;
					cut1=0;
					cut2=0;
				}
			}
		}
		printf("%d
",ans);
		for(int i=0; i<ans; ++i) {
			printf("%d %d
",ans1[i],ans2[i]);
		}
	}
	return 0;
}