D.Two Divisors
题意
给出一个数组a
要求对每个ai求出两个它的因数d1 d2
使得gcd(d1+d2,ai)=1
若不存在则d1 d2=-1
题解
先取出ai的一个素因子d1
然后取出d2=ai/d1
若d2是d1的倍数那么一直除去d1直到d2%d1!=0
d2%d1!=0保证了 (d2+d1)也不是d1的倍数 所以就能保证gcd(d2+d1,ai)!=d1
同时也能保证最终的d2仍然是ai的因子
其次为什么gcd(d2+d1,ai)一定等于1
首先取出的d1是ai的最小素因子 已经排除gcd(d2+d1,ai)=d1的可能后
依次枚举ai的其他因子x (d1<x<=d2+d1)
即证(d2+d1)不是x的倍数 因为d1<x所以 (d2+d1) mod x= d2 mod x +d1 mod x= d1 + (d2 mod x) !=0
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
41
42
43
44
45
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
# define endl '\n'
# define Turnoff std::ios::sync_with_stdio(false)
const ll Max=5e5+5;
int data[Max];
bool vis[Max];
int prime[Max],num=0;
vector<int>b1,b2;
void intn(){
for(int i=2;i<Max;i++){
if(!vis[i])prime[num++]=i;
for(int j=0;j<num&&i*prime[j]<Max;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main() {
Turnoff;
intn();
int n;cin>>n;
for(int i=0;i<n;i++){
cin>>data[i];
bool flag=0;int d1,d2;
for(int j=0;prime[j]*prime[j]<=data[i];j++){
if(data[i]%prime[j])continue;
d1=prime[j];d2=data[i]/d1;
while(d2%d1==0)d2/=d1;
if(d2!=1)flag=1;
break;
}
if(flag)b1.push_back(d1),b2.push_back(d2);
else b1.push_back(-1),b2.push_back(-1);
}
for(auto i:b1 )cout<<i<<" ";
cout<<endl;
for(auto i:b2)cout<<i<<" ";
cout<<endl;
}
|