原题链接:https://codeforces.ml/contest/1366/problem/D
题意:n个数,对于每个ai,找到ai的任意两个大于1的因子d1和d2,若gcd(d1+d2,ai)=1,怎输出d1和d2,若找不到满足条件的两个因子,则输出-1
1≤n≤500000;1≤ai≤10000000;
input
10 2 3 4 5 6 7 8 9 10 24
output
-1 -1 -1 -1 3 -1 -1 -1 2 2
-1 -1 -1 -1 2 -1 -1 -1 5 3
第一行为d1,第二行为d2
思路:
若gcd(x,y)=1,则gcd(x+y,x·y)=1
对ai进行质因数分解,则ai=(q1^k1)*( q2^k2)*(q3^k3)…*(qn^kn)
若ai是质数,结果肯定是-1
很显然q1^k1与q2^k2*q3^k3…*qn^kn是互质的
那么q1^k1 + q2^k2*q3^k3…*qn^kn与q1^k1* q2^k2*q3^k3…*qn^kn=ai也是互质的(由上面的定理可推导得知)
那么我们只需要找到ai的最小质因子即可
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[500005],n;
int prime[10005],p[40005],cnt;
int d[3][500005];
void euler(int n)
{
for(int i=2;i<=n;i++)
{
if(!p[i])
{prime[++cnt]=i;}
for(int j=1;j<=cnt;j++)
{
if(i*prime[j]>n)
{break;}
p[prime[j]*i]=1;
if(i%prime[j]==0)
{break;}
}
}
}
int main()
{
euler(10000);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{scanf("%d",&a[i]);d[1][i]=-1;d[2][i]=-1;}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=500;j++)
{
if(a[i]%prime[j]==0)
{d[1][i]=prime[j];break;}
}
}
for(int i=1;i<=n;i++)
{
if(d[1][i]==-1)
{continue;}
int op=a[i]/d[1][i];
while(op%d[1][i]==0)
{op/=d[1][i];}
if(op==1)
{d[1][i]=-1;d[2][i]=-1;}
else{
d[2][i]=op;}
}
for(int i=1;i<=n;i++)
{printf("%d ",d[1][i]);}
printf("\n");
for(int i=1;i<=n;i++)
{printf("%d ",d[2][i]);}
printf("\n");
return 0;
}
123