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

Есеп H. Оңай математика

Уақытка қойылған шектеу:

1 second

Жадқа қойылған шектеу:

256 megabytes

Абайдың $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