• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

B. Math - Codeforces

Aruba Cloud - Virtual Private Server VPS
0 głosów
225 wizyt
pytanie zadane 31 grudnia 2023 w Algorytmy przez Szyszka Gaduła (3,510 p.)

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?

1 odpowiedź

+1 głos
odpowiedź 31 grudnia 2023 przez adrian17 Mentor (352,540 p.)
wybrane 31 grudnia 2023 przez Szyszka
 
Najlepsza

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.

komentarz 31 grudnia 2023 przez Szyszka Gaduła (3,510 p.)
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ć?
komentarz 31 grudnia 2023 przez Szyszka Gaduła (3,510 p.)
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ć.
komentarz 31 grudnia 2023 przez Szyszka Gaduła (3,510 p.)
Wielkie dzięki! Działający kod: https://pastebin.com/JCjNqHmy

Podobne pytania

0 głosów
0 odpowiedzi 267 wizyt
pytanie zadane 10 marca 2024 w Algorytmy przez Dani Obywatel (1,450 p.)
0 głosów
0 odpowiedzi 121 wizyt
pytanie zadane 21 stycznia 2024 w Algorytmy przez Szyszka Gaduła (3,510 p.)
0 głosów
0 odpowiedzi 237 wizyt

93,322 zapytań

142,319 odpowiedzi

322,387 komentarzy

62,651 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...