NTRIPLETS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, find three distinct positive integers A, B, C such that the pairwise product of any two is a divisor of N, and the product of all three is a multiple of N.

EXPLANATION:

For convenience, let’s suppose 1 \leq A \lt B \lt C.
First, note that since AB, BC, AC should all be divisors of N, each of A, B, C must themselves be divisors of N.

We’d like all three to be distinct, so if N = 1 or N is prime, the answer is -1 since N doesn’t even have three distinct divisors.

Also note that C = N is impossible.

Why?

We’ll always have B \gt 1, so if C = N then BC would be strictly larger than N, and hence cannot be a divisor of it.

This further tells us that if N = p^2 for a prime p, then the answer is -1 (since p^2 doesn’t have three distinct factors smaller than it).

In every other case, finding an answer is always possible.
One simple construction is as follows: pick A = 1, B = p, C = N/p where p is some prime dividing N. It’s easy to verify that this always works when N is neither a prime nor a square of a prime.

So, we need to do the following:

  • Check whether N is prime.
  • Check whether N is the square of a prime.
  • If N is neither, find some prime divisor of N.

This is easy to do in \mathcal{O}(\sqrt N) by slightly modifying the standard primality check algorithm: simply iterate over numbers from 2 to \sqrt{N}, and the first time you find a divisor, return it.
Ensure that the divisor you return isn’t the square root of N; and if you don’t find any such divisor, the answer is -1.

TIME COMPLEXITY:

\mathcal{O}(\sqrt{N}) per testcase.

CODE:

Code (Python)
def findprime(n):
    for i in range(2, n+1):
        if i*i > n: break
        if n%i == 0: return i
    return -1

for _ in range(int(input())):
    n = int(input())
    p = findprime(n)
    if n == 1 or p == -1 or p*p == n: print(-1)
    else: print(1, p, n//p)
3 Likes

why this code didn’t work?

#include<bits/stdc++.h>
#define DilligentArch() ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define testcase(t) int t; cin>>t; while(t–)
#define endl ‘\n’
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;

void solve() {
ll n;
cin >> n;

vectorv;
for (ll i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
v.pb(i);
if (i != n / i) {
v.pb(n / i);
}
}
}

sort(v.begin(),v.end());
if(v.size()<4)cout<< “-1”<<endl;
else cout<<v[0]<<" "<<v[1]<< " "<<v[2]<<endl;

}

int main()
{
DilligentArch()
testcase(t){

    solve();
    
}

}

@dilligent4rch This code works. You didn’t insert ‘1’ element before inserting the other elements. You have to insert it outside the for loop. And break for loop after inserting elements. So you don’t need to sort the vector.

#include<bits/stdc++.h>

#define DilligentArch() ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);

#define testcase(t) int t; cin>>t; while(t–)

#define endl ‘\n’

#define F first

#define S second

#define pb push_back

#define mp make_pair

typedef long long ll;

using namespace std;

void solve() {

ll n;

cin >> n;

vectorv;

v.pb(1);

for (ll i = 2; i <= sqrt(n); i++) {

if (n % i == 0) {

v.pb(i);

if(i != n/i){

v.pb(n / i);

break;

}

}

}

// sort(v.begin(),v.end());

if(v.size()<3) cout<<-1<<endl;

else {cout<<v[0]<<" "<<v[1]<< " "<<v[2]<<endl;}

}

int main()

{

DilligentArch()

testcase(t){

solve();

}

}

Thanks random programmer…You have my respect.
thanks for helping out this newbie!!

1 Like

can anyone tell me why isn’t it working? Thanks!

#include <bits/stdc++.h>
using namespace std;
vector < int > v;
void printDivisors(int n)
{
v.push_back(1);
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
if (n/i == i)
{
v.push_back(i);
}
else
{
v.push_back(i);
v.push_back(n/i);
}
}
}
sort(v.begin(),v.end());

}

int main()
{
int t;
cin>>t;
while(t–)
{
unsigned long long int N;
cin>>N;
int a,b,c;
vector < int > vBlank ;
v = vBlank;

    printDivisors(N);
    int flag = 0;
    if(v.size() >= 3)
    {
        for(int i=0; i<v.size(); i++)
        {

            if((i+2) <v.size())///stopping condition for accessing the elements within range
            {


                if((v[i]*v[i+1]*v[i+2])%N==0 && N%(v[i]*v[i+1])==0 && N%(v[i]*v[i+2])==0 && N%(v[i+1]*v[i+2])==0 )
                {

                    a = v[i];
                    b = v[i+1];
                    c = v[i+2];
                    flag = 1;
                    break;

                }
            }

        }

    }
    if(flag == 1)
        cout<<a<<" "<<b<<" "<<c<<endl;
    else
    {
        cout<<-1<<endl;
    }


}
return 0;

}