Codeforces：两个除数

Question

这里是问题：
给你 n 个整数 a1, a2, …, an.

对于每个 ai 找到它的两个除数 d1>1 和 d2>1 这样 gcd(d1+ d2,ai)=1（其中gcd(a,b)是a和b的最大公约数）或者说不存在这样的一对。

输入：
第一行包含单个整数 n (1 ≤ n ≤ 5*10^5) — 数组 a.

的大小

第二行n个整数a1,a2,…,an(2≤ai≤10^7)——数组a.

输出：
为了加快输出速度，打印两行，每行n个整数。

第一行和第二行的第i个整数应该是对应的约数d1>1和d2>1使得gcd(d1+d2,ai)=1并且−1如果有没有这样的一对。如果有多个答案，打印其中一个。

这是我的解决方案：

#include <iostream>
#define ll long long
#define enter cout<<"\n"
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int n; cin>>n;
    int a[n] = {0};
    for(int i=0; i<n; i++) cin>>a[i];
    int d1[n] = {0}, d2[n] = {0};
    for(int i=0; i<n; i++){
        for(int j=2; j*j<=a[i]; j++){
            if(a[i]%j==0 && __gcd(j+a[i]/j, a[i])==1){
                d1[i] = j; d2[i] = a[i]/j; break;
            }
        }
        if(d1[i]==0){
            d1[i] = -1; d2[i] = -1;
        }
    }
    for(int i=0; i<n; i++){
        cout<<d1[i]<<" "; 
    } enter;
    for(int i=0; i<n; i++){
        cout<<d2[i]<<" ";
    } enter;
    return 0;
}

我找不到比这更有效的算法了。在像 n=500000 这样的大型案例中，我遇到了“超出时间限制”的问题。我怎样才能让它更有效率？感谢您提供一点帮助。

Answer 1

这里我们需要关注的最重要的事情是 gcd(d1+d2 , a[i]) = 1.

要使此条件为真，d1 和 d2 应该互质。

所以，我们需要找到 a[i] 的 2 个互质因子，为了找到这个，最小的质因子及其重数起着重要作用。

例如：

假设，N = p1^k1 * p2^k2 * ..... * pn^kn

此处，pi = 质因数，ki = pi 的重数。

60 = 2^2 * 3^1 * 5^1

最小质因数 = p1 = 2

最小质因数的重数 = 2

因此，2^2 = 4 与另一个 pi^ki，即 3^1 和 5^1 互质。

此外，2^2 = 4 与 (3^1 * 5^1)

互质

这是因为，p1^k1 与 (p2^k2 * p3^k3 * ...... * pn^kn) 互质。

所以，最终答案：

d1 = p1^k1

d2 = (p2^k2 * p3^k3 * ...... * pn^kn) = a[i]/d1

看看下面的实现，它在 Codeforces 上有 Accepted 判决：

#include <iostream>
#include <vector>
#include <cmath>

#define maxn 1e7+10

int smallestPrime[(int)maxn];

std::vector<int> primes;

void primeFactorization(){

    primes.push_back(2);

    smallestPrime[0] = smallestPrime[1] = 1;
    for ( int i = 2 ; i < maxn ; i += 2 )
        smallestPrime[i] = 2;

    for ( int i = 3 ; i <  maxn ; i += 2 ) {
        if ( smallestPrime[i] == 0 ){
            smallestPrime[i] = i;
            primes.push_back(i);
            for ( int j = i ; j*(long long)i <  maxn ; j += 2 ) {
                if(smallestPrime[ i*j ] == 0)
                    smallestPrime[ i*j ] = i;
            }
        }
    }
}

int main(){

    primeFactorization();

    int n;
    std::cin>>n;

    int arr[1000000];
    for(int i=0;i<n;i++){
        std::cin>>arr[i];
    }

    int d1[1000000];
    int d2[1000000];

    for(int i=0;i<n;i++){

        int tmp = arr[i];
        int p1 = smallestPrime[tmp];
        int k1 = 0;
        while(tmp > 1 && p1 == smallestPrime[tmp])
            tmp /= smallestPrime[tmp],++k1;

        d1[i] = pow(p1, k1);
        
        d2[i] = arr[i]/d1[i];

        if(d1[i]==1 || d2[i]==1){
            d1[i]=-1;d2[i]=-1;
        }

    }

    for(int i=0;i<n;i++){
        std::cout<<d1[i]<<" ";
    }

    std::cout<<std::endl;


    for(int i=0;i<n;i++){
        std::cout<<d2[i]<<" ";
    }

    return 0;
}

结论：

Codeforces：两个除数

Codeforces: Two Divisors

c++

arrays

algorithm

greatest-common-divisor