Ошибка
Ваш способ не работает из-за ошибок округления и неправильного применения конструкции (int)
. И long double
не лучше чем double
в этой ситуации.
Пусть n = 125
.
Выражение pow(125, 1.0/3.0)
вычисляется в 4.999999999999999
. Так может быть: для функции возведения в степень нет гарантий точного результата, даже если этот результат представим в виде double
без искажений. :(
Выражение floor(4.999999999999999 * 1000000) / 1000000
вычисляется в 4.999999
. Здесь сознательно занижается точность, но это не беда.
Выражение (int)4.999999
вычисляется в 4
. Ошибка тут. Малая до сих пор ошибка округления стала катастрофой.
Округление можно поправить с (int)
на round
и этот случай вычислится правильно. Зато перестанут правильно вычислятся такие вещи:
2**29 = 536870912
pow(536870911, 1.0/29.0) = 1.9999999998715416
pow(536870912, 1.0/29.0) = 2.0
pow(536870913, 1.0/29.0) = 2.000000000128458
Исправление
Пусть p
- степень которую мы проверяем. Вычислим корень степени p
и расстояние от корня до ближайшего целого:
double root = std::pow(n, 1. / p);
double error = std::abs(root - std::round(root));
Даже если у числа есть точный корень степени p
ошибка может не быть равной нулю. Если у корня нет точного корня степени p
можно надеятся что ошибка будет достаточно велика. Проверить можно на всех числах n
. Несколько часов на миллиард тестов и результат готов. Если число степенное, то ошибка не больше 3.41061e-13. Если число не степенное, то ошибки для всех степеней не меньше 1.28458e-10. Ура! Вот работающий вариант:
bool powerful(int n) {
int powers[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
for (int p : powers) {
double root = std::pow(n, 1. / p);
double error = std::abs(root - std::round(root));
if (error < 1e-11) {
return true;
}
}
return false;
}
Эта функция быстрее всех: десять раз извлекаем корень и проверяем расстояние до целого. Всё. Единственное что трудно объяснить, так это почему она работает и что такое 1e-11
.
Другое решение
Чтобы найти ошибки в предыдущем разделе нужно знать какие числа степенные а какие нет. Здесь приводится другой метод выяснения степенности числа.
Из целого числа 0 <= n <= 10^9
извлечём корни простой степени от 2 до 29. Полученные корни округлим и возведём обратно в соответствующие степени. Возводить нужно точно. Результаты сравним с n
. Если есть совпадение - n
степенное число.
Простых степеней достаточно, так если n
- степенное число по составной степени, то n
- степенное и по любому делителю степени: n = r^(ab) = (r^a)^b
.
bool powerful(int n) {
int powers[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
for (int p : powers) {
double root = std::round(std::pow(n, 1. / p));
if (pow(root, p) == n) {
return true;
}
}
return false;
}
Функция возведения в степень самая простая, но точная. double
выбран так как для целых возможно переполнение, которое не хочется контролировать (позже выяснилось что переполнения именно в этой задаче не бывает никогда). Вещественные числа в нужном нам диапазоне перемножаются точно. Иначе говоря, что double
, что long long
будут вести себя одинаково в нашей задаче:
double pow(double k, int p) {
double r = 1;
for (int i = 0; i < p; ++i) {
r *= k;
}
return r;
}
Этот способ также проходит проверку на e-olymp. Он проще разложения на простые, работает быстрее.
1
как степенное число.8 = 2 * 2 * 2
, а так же я видел что степенное число это31 = 2^2 + 3^3