Вывести числа m,k такие, что m^2=(k^3)*n

@Alemano · Регистрация: 03.10.2015

Author24 — интернет-сервис помощи студентам

Помогите решить задачу

Исходные данные:
Единственная строка содержит целое число n (1 ≤ n ≤ 10^9).

Результат:
В первой строчке выведите целое число m. Во второй — целое число k. m^2 должно равняться (k^3)·n; 1 ≤ m, k ≤ 10^100.

Например:
n = 18, m = 12, k = 2.

Байт · 04.12.2015, 23:39

Alemano, Задача интересная. У вас есть какие-то соображения на этот счет? Или вы хотите, чтобы мы ее решили за вас, а вы прошли бы в следующий тур Олимпиады? На плечах людей, вам совершенно незнакомых. Уверяю вас, этот финт скорее всего не пройдет. Ибо на каком-то этапе все-таки вас попросят объяснить, что именно вы делаете. И на этом этапе вы не просто провалитесь, а не дадите дойти до него людям, соображающим своим умом. Поэтому я принципиально и активно против помощи в решении олимпиадных задач.
Ведь Олимпиады делаются для выявления соображающих ребят, а не тех, кто шустрее в Интернете.
Дурака я попробую научить. Но подлецу руки не подам.

@Голубь Вася · 04.12.2015, 23:49

Нету ограничения для m, взял самое большое которое только смог найти
В опщем как то так

C++

#include <iostream>
 
using namespace std;
 
int main() {
    unsigned long long int n = 0;
    unsigned long long int k;
    unsigned long long int m;
    cin >> n;
    for (m = 1; m < 18446744073709551615; m++) {
        for (k = 1; m * m > k * k * k * n && k < 18446744073709551615; k++);
        if (m * m == k * k * k * n) {
            cout << m << endl << k << endl;
            break;
        }
    }
    system("pause");
    return 0;
}

Добавлено через 1 минуту

Сообщение от Байт

Alemano, Задача интересная. У вас есть какие-то соображения на этот счет? Или вы хотите, чтобы мы ее решили за вас, а вы прошли бы в следующий тур Олимпиады? На плечах людей, вам совершенно незнакомых. Уверяю вас, этот финт скорее всего не пройдет. Ибо на каком-то этапе все-таки вас попросят объяснить, что именно вы делаете. И на этом этапе вы не просто провалитесь, а не дадите дойти до него людям, соображающим своим умом. Поэтому я принципиально и активно против помощи в решении олимпиадных задач.
Ведь Олимпиады делаются для выявления соображающих ребят, а не тех, кто шустрее в Интернете.
Дурака я попробую научить. Но подлецу руки не подам.

Эх, не увидел я твоего сообщения.
А задача интересная, да.
>.<

@Alemano · 05.12.2015, 00:39 **[ТС]**

Спасибо)) Да, это олимпиадная задача. Но я не участвую в олимпиадах. Преподаватель задаёт нам эти задачи в качестве домашних. Естественно, не все могут решать их. Лично мне не хватает мозгов.

Байт · 05.12.2015, 14:11

Не по теме:

Alemano, Прошу прощения за резкие слова. Очень рад, что к вам они не имеют отношения. Просто, знаете, кипело - кипело, и вот вырвалось

Добавлено через 6 минут
Голубь Вася, учитывая, что k <=10¹⁰⁰, без длинной арифметики здесь, похоже, не обойтись.
И ваш код хоть и решает логически задачу, но уж больно большой здесь перебор. И неоправданно.

Добавлено через 13 минут
По поводу перебора...
Для каждого m имеет смысл начинать перебор с k = (int) pow((double)n/(m*m), 1.0/3) и заканчивать его(break), как только k*k*k > n*m*m

@_Ivana · 05.12.2015, 18:18

Сообщение от Байт

учитывая, что k <=10^100, без длинной арифметики здесь, похоже, не обойтись.

Все проще. Факторизуем n (оно вполне разумное и факторизуется), если его множители можно сгруппировать так, что n представимо в виде n = a*a*b, тогда m = a*b*b, k = b. Все. Кота писать лень.

UPD вести с полей - конечно же факторизовать не надо, достаточно найти полный квадрат - однострочник (m может не влезть в int, лучше его (но только его) считать в длинном типе):

C++

1
2
3

int f(int n, int i) {return i*i>n ? 1 : n%(i*i)==0 ? i : f(n, i+(i==2 ? 1 : 2));}
 
int main() {int n,a,k; cin>>n; a=f(n,2),k=n/a/a; cout<<"m = "<<a*k*k<<", k = "<<k;}

А вообще можно ничего не считать и сразу выдать:

C++

1	int main() {int n; cin>>n; cout<<"m = "<<n*n<<", k = "<<n;}

А вы говорите перебор, циклы и длинная арифметика... Как программисты, ей б...гу

Добавлено через 12 минут
ЗЫ вспомнил, что Tulosba предлагал за такие прозрачные и очевидные тернарные цепочки руки отрывать, а иные ссылались на книги, в которых тернарки вообще запрещали

@SlavaSSU · 05.12.2015, 18:44

_Ivana,

C++ (Qt)

1	cout << "m == " << n * 1LL * n << endl;

zer0mail · 05.12.2015, 18:48

Сообщение от Alemano

Преподаватель задаёт нам эти задачи в качестве домашних.

Преподаватель хочет оценить ваши способности или умение скопипастить ответ с форума?

Байт · 05.12.2015, 20:33

Сообщение от _Ivana

А вообще можно ничего не считать и сразу выдать:

Сообщение от SlavaSSU

cout << "m == " << n * 1LL * n << endl;

Ребят! Я чегой-то не врубаюсь. В чем шутка юмора? Объясните убогому.
Не исключаю резкое понижение собственных возможностей на фоне двухдневного хождения по гостям. Однако, сколь я ни пялился на ваши предложения, так никуды и не впялился.

@_Ivana · 05.12.2015, 21:31

SlavaSSU, ага, или 1LL первым множителем, чтобы дать понять компилятору тип переменной.

Байт, шутка юмора в том, что при разных n задача имеет разное количество решений, но тривиальное есть всегда. Кстати, из примера ТС не следует, но подразумевается минимальное решение. Тогда в моем коте надо искать полный квадрат с конца - с корня четвертой степени вниз до 1.

@Alemano 0 / 0 / 0 Регистрация: 03.10.2015 Сообщений: 25
		1
	Вывести числа m,k такие, что m^2=(k^3)n 04.12.2015, 23:10. Показов* 1643. Ответов 9 Метки нет (Все метки) Помогите решить задачу Исходные данные: Единственная строка содержит целое число n (1 ≤ n ≤ 10^9). Результат: В первой строчке выведите целое число m. Во второй — целое число k. m^2 должно равняться (k^3)·n; 1 ≤ m, k ≤ 10^100. Например: n = 18, m = 12, k = 2. 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	04.12.2015, 23:39	2
	Alemano, Задача интересная. У вас есть какие-то соображения на этот счет? Или вы хотите, чтобы мы ее решили за вас, а вы прошли бы в следующий тур Олимпиады? На плечах людей, вам совершенно незнакомых. Уверяю вас, этот финт скорее всего не пройдет. Ибо на каком-то этапе все-таки вас попросят объяснить, что именно вы делаете. И на этом этапе вы не просто провалитесь, а не дадите дойти до него людям, соображающим своим умом. Поэтому я принципиально и активно против помощи в решении олимпиадных задач. Ведь Олимпиады делаются для выявления соображающих ребят, а не тех, кто шустрее в Интернете. Дурака я попробую научить. Но подлецу руки не подам. 0

@Alemano 0 / 0 / 0 Регистрация: 03.10.2015 Сообщений: 25
	05.12.2015, 00:39 [ТС]	4
	Спасибо)) Да, это олимпиадная задача. Но я не участвую в олимпиадах. Преподаватель задаёт нам эти задачи в качестве домашних. Естественно, не все могут решать их. Лично мне не хватает мозгов. 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	05.12.2015, 14:11	5
	Не по теме: Alemano, Прошу прощения за резкие слова. Очень рад, что к вам они не имеют отношения. Просто, знаете, кипело - кипело, и вот вырвалось Добавлено через 6 минут Голубь Вася, учитывая, что k <=10¹⁰⁰, без длинной арифметики здесь, похоже, не обойтись. И ваш код хоть и решает логически задачу, но уж больно большой здесь перебор. И неоправданно. Добавлено через 13 минут По поводу перебора... Для каждого m имеет смысл начинать перебор с k = (int) pow((double)n/(mm), 1.0/3) и заканчивать его(break), как только kkk > nm*m 0

zer0mail 2686 / 2258 / 244 Регистрация: 03.07.2012 Сообщений: 8,219 Записей в блоге: 1
	05.12.2015, 18:48	8
	Сообщение от Alemano Преподаватель задаёт нам эти задачи в качестве домашних. Преподаватель хочет оценить ваши способности или умение скопипастить ответ с форума? 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	05.12.2015, 20:33	9
	Сообщение от _Ivana А вообще можно ничего не считать и сразу выдать: Сообщение от SlavaSSU cout << "m == " << n * 1LL * n << endl; Ребят! Я чегой-то не врубаюсь. В чем шутка юмора? Объясните убогому. Не исключаю резкое понижение собственных возможностей на фоне двухдневного хождения по гостям. Однако, сколь я ни пялился на ваши предложения, так никуды и не впялился. 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	05.12.2015, 21:31	10
	SlavaSSU, ага, или 1LL первым множителем, чтобы дать понять компилятору тип переменной. Байт, шутка юмора в том, что при разных n задача имеет разное количество решений, но тривиальное есть всегда. Кстати, из примера ТС не следует, но подразумевается минимальное решение. Тогда в моем коте надо искать полный квадрат с конца - с корня четвертой степени вниз до 1. 0

Вывести числа m,k такие, что m^2=(k^3)*n

Решение