General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
69416382 Practice:
ameya
1294C - 18 GNU C++14 Accepted 436 ms 72 KB 2020-01-23 16:13:14 2020-01-23 16:13:14
 
 
→ Source
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <utility>
#include <deque>
#include <chrono>
#include <random>
#include <set>
#include <cmath>
#include <ctime>
#include <bitset>

typedef long long ll;

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time_init() clock_t clock_start = clock()
#define time_now()  debug("Time since start: %.3f seconds.\n", (double)(clock() - clock_start) / CLOCKS_PER_SEC)

using namespace std;

int exp(int base, int pow){
    if(base == 1){
        return 1;
    }

    if(pow == 0){
        return 1;
    }

    if(pow == 1){
        return base;
    }

    int halfmod = exp(base, pow/2);
    if(pow % 2){
        halfmod *= base;
    }
    return halfmod;
}

void print(set<int>& s){
    for(auto x: s){
        cout << x << " ";
    }
    cout << "\n";
}

bool valid(set<int>& s, int n){
    if(s.size() != 3){
        return false;
    }

    for(auto x: s){
        if(x < 2){
            return false;
        }
    }

    for(auto x: s){
        n /= x;
    }

    if(n == 1){
        return true;
    } else {
        return false;
    }
}

// Do sieve till root.
const int N = 1e9 + 10;
const int Nsqrt = sqrt(N) + 1;
bitset<Nsqrt + 1> is_prime;
vector<int> primes;

void sieve(){
    is_prime.set();
    is_prime.reset(1);

    for (int i = 2; i <= Nsqrt; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= Nsqrt; j += i){
                is_prime.reset(j);
            }
        }
    }
}

int main(){

    sieve();

    int t;
    cin >> t;
    
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937 mt(seed);
    uniform_real_distribution<double> dist(0.0, 1.0);

    for(int test = 0; test < t; ++test){
        int n;
        cin >> n;

        if(n < 8){
            cout << "NO" << "\n";
            continue;
        }

        int n_dash = n;
        map<int, int> factors;
        for(auto p: primes){
            while(n_dash % p == 0){
                factors[p] += 1;
                n_dash /= p;
            }
        }

        if(n_dash > 1){
            factors[n_dash] += 1;
        }

        bool done = false;
        for(int iter = 0; iter < 10000; ++iter){
            set<int> ans;
            
            int a = -1;
            for(auto entry: factors){
                if(dist(mt) >= 0.5){
                    auto pow = 1 + dist(mt) * entry.second;
                    a = exp(entry.first, pow);
                    break;
                }
            }

            if(a == -1){
                continue;
            }

            int b = -1;
            for(auto entry: factors){
                if(dist(mt) >= 0.5){
                    auto pow = 1 + dist(mt) * entry.second;
                    b = exp(entry.first, pow);

                    if(b != a){
                        break;
                    }
                }
            }

            if(b == -1){
                continue;
            }

            ans.insert(a);
            ans.insert(b);
            ans.insert(n/(a * b));

            if(valid(ans, n)){
                cout << "YES" << "\n";
                for(auto x: ans){
                    cout << x << " ";
                }
                cout << "\n";
                done = true;
                break;
            }
        }

        if(!done){
            cout << "NO" << "\n";
        }

    }
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details