ГЖО 7-8 класс 2019 год

Задача H. Легкая математика

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

У Абая есть натуральное число $n$. Он может делать с этим числом 2 вида операций: 1) Умножить $n$ на $x$ ($x$ — любое натуральное число) 2) Заменить $n$ на $\sqrt{n}$ (в этом случае $\sqrt{n}$ должно быть целым числом) Обе операции можно делать любое количество раз. Помогите Абаю узнать, какое минимальное число можно получить, выполняя данные операции. Также Абая интересует, какое минимальное количество операций нужно проделать, чтобы получить минимальное число.

Формат входного файла

В единственной строке дано натуральное число $n$ ($1 <= n <= 10^6$).

Формат выходного файла

Выведите два числа: минимальное число, которое можно получить, затем минимальное количество операций для получения этого числа.

Примеры:

Вход

20

Ответ

10 2

Вход

5184

Ответ

6 4

Замечание

Ответ для первого примера: 20 --> $20 \times 5 = 100$ --> $\sqrt{100} = 10$ — в итоге 2 операции. Ответ для второго примера: 5184 --> $\sqrt{5184} = 72$ --> $72 \times 18 = 1296$ --> $\sqrt{1296} = 36$ --> $\sqrt{36} = 6$ — в итоге 4 операции. ( Abay Baimukanov )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define pb push_back
#define si size()

using namespace std;

const int inf = 2e9;

map<int, int> del;

bool if_prost(int n)
{
	int i = 2;
	while(i * i <= n)
	{
		if(n % i == 0)
			return 0;
		i++;
	}
	return 1;
}

void rdel(int n)
{
	int i = 2;
	while(n != 1)
	{
		if(if_prost(i))
		{
			if(n % i == 0)
				del[i] = 0;
			while(n % i == 0)
			{
				del[i]++;
				n /= i;
			}
		}
		i++;
	}
}

int main()
{
    int n;
    cin >> n;
    if(n == 1)
    {
    	cout << "1 0";
    	return 0;
	}
    rdel(n);
    int m = -1;
    vector<int> cols;
    int ans = 1;
    for(map<int, int>::iterator it = del.begin(); it != del.end(); ++it)
    {
    	int ff = (it->first), ss = (it->second);
    	if(m < ss)
    	{
    		m = ss;
		}
    	//cout << ff << ": " << ss << endl;
    	ans *= ff;
    	cols.pb(ss);
	}
	sort(cols.begin(), cols.end());
	if(cols.back() == cols[0])
	{
		int st = cols[0];
		int ii = 0;
		while(st % 2 == 0)
		{
			st /= 2;
			ii++;}
		if(ii == 0 && st == 1)
		{
			cout << n << ' ' << 0;
			return 0;
		}
		if(st == 1)
		{
			cout << ans << ' ' << ii;
			return 0;
		}
	}
	int kk = ceil(log2(m));
	cout << ans << ' ' << kk + 1;
}

Можетн скинуть решение с оператором if, elif без цикла???

Нет такого

показать/скрыть код

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0)
#define sz(a) (a).size()


using namespace std;

const ll N = 1e6 + 10;
const ll big = 1e18;
const ll block = 800;
const ll mod = 1e6;

ll dp[N];

ll n;

ll sp[N];

ll ans = 1;

ll z = 0;

ll mx = 0;

int main() {
    speed;
	cin >> n;
	vector<ll> x;
	for(int i = 2; i * i <= n; i++) {
		if(n % i == 0) {
			x.pb(i);
			while(n % i == 0)
				sp[x.size() - 1]++, n /= i;
		} 
	}
	if(n != 1)
		x.pb(n),sp[x.size() - 1] = 1;
	for(ll i = 0 ; i < x.size() ; i++) {
		ll y = log2(sp[i]);
		ans *= x[i];
		if(1ll << y != sp[i])
			mx = 1,y++;
		if(i && z != y)
			mx = 1;
		z = max(z, y);
	}
	cout << ans << " " << z + mx << '\n';
	
}

//ZA

#include <bits/stdc++.h>

#define o cout<<"Hello did you expect this?"<<endl;

#define ll long long

#define pb push_back

#define mp make_pair//with Z

#define F first

#define S second

using namespace std;

const int N = 2e5 + 100;

const int mod = 1e9 + 7;

void hey () {

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

}

int main () {

hey();

int x;

cin >> x;

map<int,int> was;

vector<int> factors;int wow = x;

for (int i = 2; i <= sqrt(x); i++) {

while (x % i == 0) {

factors.push_back(i);

x /= i;

}

}

if (x != 1) {

factors.push_back(x);

}

bool hm2 = 0;

for (int i = 0; i < factors.size(); i++) {

was[factors[i]]++;

if (was[factors[i]] > 1) {

hm2 = 1;

}

}

if (hm2) {

int ans = 0;

int dov = 0;

for (int i = 1; i <= 30; i++) {

int k = (1 << i);

bool no = 0;

bool was2 = 0;

for (int i = 0; i < factors.size(); i++) {

if (k < was[factors[i]]) {

no = 1;

}

if (k > was[factors[i]]) {

was2 = 1;

}

}

if (!no) {

ans = i;

if (was2) {

ans++;

}

break;

}

}

int hm = 1;

for (int i = 1; i <= 1e4; i++) {

if (was[i]) {

hm *= i;

}

}

cout << hm << " " << ans;

}

else {

cout << wow << " " << 0;

}

}

Можно было лучше написать конечно.

Обьяснения кода:

Есть теорема

N = p1 ^ k1 * p2 ^ k2 * p3 ^ k3......

p1, p2, p3= простые числа(различные)

k1, k2, k3(сколько они раз встречаются в разложение числа N)

по этой теореме верно то что

sqrt(N) = p1 ^ (k1 / 2) * p2 ^ (k2 / 2) * p3 ^ (k3 / 2)

k1, k2, k3 должны делиться на 0.

А ответ будет равняться произведению всех простых чисел. И значит мы можем умножить наше число N чтобы k1, k2, k3.. было степень двойки. После этого мы можем просто пока у нас k1, k2, k3 != 1 делать sqrt(N) то есть из за этого у нас ответ log2 + 1 или просто log2