题目链接：D：Two Divisors
题意：
给你n个数，对于每一个数vi，你需要找出来它的两个因子d1，d2。这两个因子要保证gcd(d1+d2,vi)==1。输出的时候输出两行，第一行输出每一个数vi对应的第一个因子d1，第二行对应位置输出第二个因子d2
题解：
最大公约数有两个基本性质如下：
- gcd(a,b)=gcd(a±b,b)=gcd(a,b±a);
- if(gcd(a,b)==1) gcd(a,bc)=gcd(a,c);
设p1、p2、p3...pm是一个数x的所有质因子，我们设d1=p1^k(它的意思就是p1的k次方)，d2=x/d1。这个k要保证d2%p1!=0
而且还会有x=p1^k1*p2^k2*...*pk^km=d1*d2
我们很容易就知道gcd(d1,d2)==1，毕竟d1是质因子p1的平方所得
那么gcd(d1,d2)=gcd(d1+d2,d1)=gcd(d1+d2,d2)，又因为x=d1*d2
所以d1+d2就和x互质
因为样例有好多组，所以我们就先通过线性筛的方法进行预处理，具体看代码：
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<deque>
7 #include<string.h>
8 #include<map>
9 #include <iostream>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 const int maxn=1e7+10;
14 int minprim[maxn],prim[maxn],v[maxn],ans1[maxn],ans2[maxn];
15 int finds(int n) //线性筛
16 {
17 int num=0; //num为从2到maxn这个范围内所有质数（也就是素数）的个数
18 for(int i=2;i<=n;++i)
19 {
20 //minprim数组里面保存的是i的最小质因子（所谓质因子也就是为素数的因子）
21 if(!minprim[i]) prim[++num]=i,minprim[i]=i;
22 for(int j=1;j<num && prim[j]*i<=n;++j)
23 {
24 minprim[i*prim[j]]=prim[j];
25 }
26 }
27 return num;
28 }
29 int main()
30 {
31 int n;
32 finds(1e7);
33 scanf("%d",&n);
34 for(int i=1;i<=n;++i)
35 scanf("%d",&v[i]);
36 //printf("%d***\n",minprim[24]);
37 for(int i=1;i<=n;++i)
38 {
39 int ans=minprim[v[i]],temp;
40 v[i]/=ans;
41 temp=ans;
42 while(v[i]%ans==0) v[i]/=ans,temp*=ans;
43 if(v[i]==1)
44 ans1[i]=ans2[i]=-1;
45 else ans1[i]=temp,ans2[i]=v[i];
46
47 }
48 for(int i=1;i<=n;++i)
49 {
50 if(i==n) printf("%d\n",ans1[i]);
51 else printf("%d ",ans1[i]);
52 }
53 for(int i=1;i<=n;++i)
54 {
55 if(i==n) printf("%d\n",ans2[i]);
56 else printf("%d ",ans2[i]);
57 }
58 return 0;
59 }