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
?
?
?
?