CF1366D 题解
$\text{Description}$
给定 $n$ 个数，对每个数 $a$ 求出一对正整数 $x,y$ 满足 $x|a,y|a,\gcd(x+y,a)=1$。
$n\le 5\times 10^5,a\le 10^7$
$\text{Solution}$
设 $d=\gcd(x,y),x’=x/d,y’=y/d$，则 $x+y=d(x’+y’)$，注意到 $d|a$，则 $\gcd(d(x’+y’),a)\ge d$，故 $d$ 只能为 $1$，即 $x,y$ 互质。
那么我们选择 $a$ 的最小质因子，并取 $x$ 为其在 $a$ 中的最大幂，取 $y$ 为 $a/x$ 即可。
若一个数为质数幂，则无解。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
const int U=10000005;
int n;
int Vis[U],Prm[U],cnt,Lef[U],Div[U],tmp,D1[500005],D2[500005];
inline void Euler(){
Lef[U]=1,Div[U]=0;
for(REG int i=2;i<=U-5;++i){
if(!Vis[i]) Prm[++cnt]=i,Lef[i]=i,Div[i]=1;
for(REG int j=1;j<=cnt&&i*Prm[j]<=U-5;++j){
Vis[i*Prm[j]]=1;
if(!(i%Prm[j])) Lef[i*Prm[j]]=Lef[i]*Prm[j],Div[i*Prm[j]]=Div[i];
else Lef[i*Prm[j]]=Prm[j],Div[i*Prm[j]]=Div[i]+1;
}
}
}
inline void Work(){
read(n),Euler();
for(REG int i=1;i<=n;++i){
read(tmp);
if(Div[tmp]<=1) D1[i]=D2[i]=-1;
else D1[i]=Lef[tmp],D2[i]=tmp/Lef[tmp];
}
for(REG int i=1;i<n;++i) printf("%d ",D1[i]);
printf("%d\n",D1[n]);
for(REG int i=1;i<=n;++i) printf("%d ",D2[i]);
}
int main(){Work();}
|
