Codeforces: Two Divisors

Question

Here is the question:
You are given n integers a1, a2, …, an.

For each ai find its two divisors d1>1 and d2>1 such that gcd(d1+d2,ai)=1 (where gcd(a,b) is the greatest common divisor of a and b) or say that there is no such pair.

Input:
The first line contains single integer n (1 ≤ n ≤ 5*10^5) — the size of the array a.

The second line contains n integers a1,a2,…,an (2 ≤ ai ≤ 10^7) — the array a.

Output:
To speed up the output, print two lines with n integers in each line.

The i-th integers in the first and second lines should be corresponding divisors d1>1 and d2>1 such that gcd(d1+d2,ai)=1 and −1 if there is no such pair. If there are multiple answers, print any of them.

Here is my solution:

#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;
}

I couldn't find an algorithm more efficient than this. I am getting "Time limit exceeded" on a large case like n=500000. How can I make it more efficient? A little help is appreciated.

Answer 1

The most important thing we need to focus here is gcd(d1+d2 , a[i]) = 1.

For this condition to be true, d1 and d2 should be coprimes.

So, we need to find the 2 coprime divisors of a[i] and to find this, the smallest prime factor and it's multiplicity plays a big role.

For eg:

Suppose, N = p1^k1 * p2^k2 * ..... * pn^kn

Here, pi = prime factor, ki = multiplicity of pi.

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

Smallest prime factor = p1 = 2

Multiplicity of smallest prime factor = 2

So, 2^2 = 4, is coprime with the other pi^ki, i.e., 3^1 and 5^1.

Also, 2^2 = 4 is coprime with (3^1 * 5^1)

This is because, p1^k1 is corprime with (p2^k2 * p3^k3 * ...... * pn^kn).

So, Final Answer:

d1 = p1^k1

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

Have a look at the following implementation which has Accepted verdict on Codeforces:

#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;
}

Verdict: