B. Math - Codeforces

Question

Witam,
Takie oto zadanko:
https://codeforces.com/problemset/problem/1062/B
 

Zalicza mi testy do 9, wtedy się wywala, input = 786432. Output powinien być równy 6 6, a mój kod daje odpowiedź 6 9. Rozumiem, że coś jest źle z moim podejściem, bo nawet nie mogę sobie wyobrazić jak do tego wyniku 6 6 mam dojść. Oto kod:
 

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

using namespace std;

map<int, int> factorize(int n) {
	vector<int> sieve(n + 1, 1);
	sieve[0] = sieve[1] = 0;

	for (int i = 2; i <= n; ++i) {
		if (sieve[i] != 1)
			continue;

		for (long long j = 1LL * i * i; j <= n; j += i) {
			sieve[j] = i;
		}
	}

	if (sieve[n] == 1)
		return { {1, 1}, {n, 1} };

	map<int, int> prime_factors;
	while (sieve[n] > 1) {
		++prime_factors[sieve[n]];
		n /= sieve[n];
	}

	++prime_factors[n];
	return prime_factors;
}

vector<int> solve(int n) {
	map<int, int> prime_factors = factorize(n);
	vector<int> result(2);
	result[0] = 1;

	int max_exp = 0;
	bool can_sqrt = true;
	for (const pair<const int, int>& factor : prime_factors) {
		max_exp = max(max_exp, factor.second);

		if ((factor.second & 1) != 0)
			can_sqrt = false;

		result[0] *= factor.first;
	}

	if (!can_sqrt) {
		++result[1];

		// We can align maximum exponent in one step (while aligning others exponents to be even), so check if its needed
		if ((max_exp & 1) != 0)
			++max_exp;
	}

	while (max_exp > 1) {
		if ((max_exp & 1) == 0) {
			max_exp /= 2;
		}
		else {
			++max_exp;
		}

		++result[1];
	}

	return result;
}

int main()
{
	int n;
	cin >> n;

	vector<int> result = solve(n);
	cout << result[0] << " " << result[1];
}

Idea jest taka: znaleźć rozkład na liczby pierwsze, i jeśli się da to pierwiastkować, a jeśli nie to mnożyć (żeby w każdej potędze jej wykładnik był równy najwyższemu wykładnikowi ze wszystkich obecnych w rozkładzie na liczby pierwsze). Pierwiastek kwadratowy to jest wykładnik 1/2, więc dziele moje wszystkie wykładniki na 2. W ten sposób dochodzę w końcu do wykładnika 1, iloczyn tych liczb to moja minimalna liczba, a ilość operacji zliczam w trakcie.
Coś takiego:

Tak, widzę pattern, pewnie można kod mocno skrócić, ale na razie to zostawmy skoro jest przypadek dla którego to nie działa.

W jaki inny sposób mógłbym liczyć minimalną liczbę operacji?

Answer 1

nawet nie mogę sobie wyobrazić jak do tego wyniku 6 6 mam dojść

Hint: spójrz na swój rysunek z listą operacji i skup się na mnożeniach.

Comments

Patrzę, patrzę, patrzę... Nic nie widzę. No oprócz tego, że mnożeniem zawsze zwiększam wykładniki o 1. Ale co z tym mogę zrobić?

---

Aaa, dobra. Po prostu muszę to na początku pomnożyć żeby uzyskać liczbę 2^X, wtedy będę mógł cały czas pierwiastkować.

---

Wielkie dzięki! Działający kod: https://pastebin.com/JCjNqHmy