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?