Educational Codeforces Round 89 (Rated for Div. 2)D. Two Divisors 线性筛质因子

题目链接:D:Two Divisors

题意:

给你n个数,对于每一个数vi,你需要找出来它的两个因子d1,d2。这两个因子要保证gcd(d1+d2,vi)==1。输出的时候输出两行,第一行输出每一个数vi对应的第一个因子d1,第二行对应位置输出第二个因子d2

题解:

最大公约数有两个基本性质如下:

  1. gcd(a,b)=gcd(a±b,b)=gcd(a,b±a);
  2. 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***
",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
",ans1[i]);
51         else printf("%d ",ans1[i]);
52     }
53     for(int i=1;i<=n;++i)
54     {
55         if(i==n) printf("%d
",ans2[i]);
56         else printf("%d ",ans2[i]);
57     }
58     return 0;
59 }
原文地址:https://www.cnblogs.com/kongbursi-2292702937/p/13299709.html