Educational Codeforces Round 89（D. Two Divisors）数论

原题链接：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；

10
2 3 4 5 6 7 8 9 10 24

-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