欧拉筛筛出最小素因数

本文主要是介绍欧拉筛筛出最小素因数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个是个板子题。

Educational Codeforces Round 89D. Two Divisors

题目链接

https://codeforc.es/contest/1366/problem/D

题意

找到a的两个因数，使得两个因数的和与原数a互素。一共2e5个a要弄。

吐槽

这道题一看就是个构造题。挺难的。我开始觉得自己找到了方法，后来被队长叉掉了。难就难在很难想到构造的方法。但是想到了就很简单了。场上不少人过掉了，但我不会。赛后群里讨论我的想法被发现是个假算法，其他人也都不太会。完了看看官方题解恍然大悟。

题解

画log的时间把a分解质因数了，如果只有一个质因数，那肯定不行。如果有多个，那么把这些质因数随便分成非空的两组，每组乘积就是答案。为什么是这样呢？

• 证明：
  • 令$$\begin{gathered} d_1=p_1\cdot p_2\cdot ...\cdot p_x \\ {d}_2=p_{x+1}\cdot p_{x+2}\cdot ...\cdot p_n \end{gathered}$$
  • 对于任何一个质因数$p_i$，它一定只被$d_1{d}_2$其中之一整除，所以一定不会被$d_1+d_2$整除。所以$d_1+d_2$和a不可能有公约数。
  • 如果有的话，一定是某个$p_i$，而任意一个$p_i$都不可能整除$d_1+d_2$，所以互素。

这样就很好做了。然而我居然没想到。。。

AC代码(欧拉筛板子)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int NN=1e7+10;
int prime[NN];
int visit[NN];
int minDiv[NN];
const int nn=5e5+10;
int d1[nn],d2[nn];
void Prime(int n){memset(visit,0,sizeof(visit));for (int i = 2;i <= n; i++) {if (!visit[i]) {prime[++prime[0]]=i;minDiv[i]=i;}for (int j = 1; j <=prime[0] && i*prime[j] <=n; j++) {visit[i*prime[j]] = 1;minDiv[i*prime[j]]=prime[j];if (i % prime[j] == 0) {break;}}}
}
int main(){Prime(1e7);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);int xx=1;while(x>1){if(xx%minDiv[x]){xx*=minDiv[x];}x/=minDiv[x];}int cd1=minDiv[xx];int cd2=xx/cd1;if(cd2%cd1==0||cd1%cd2==0){d1[i]=-1;d2[i]=-1;}else{d1[i]=cd1;d2[i]=cd2;}}for(int i=1;i<=n;i++){printf("%d ",d1[i]);}printf("\n");for(int i=1;i<=n;i++){printf("%d ",d2[i]);}printf("\n");return 0;
}

这篇关于欧拉筛筛出最小素因数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---