Быстрый способ найти несчастный номер

Question

Быстрый способ найти несчастный номер

Я пытаюсь решить вопрос. По заданному диапазону целых чисел пользователь должен найти количество несчастных, присутствующих в данном диапазоне.

Несчастный номер— число n такое, что повторение этой карты суммы квадратов, начинающейся с n, никогда не достигает числа 1.

Я пытался использовать метод грубой силы, вычисляя сумму квадратов цифр, и если в любой момент она равна любому из них (4, 16, 37, 58, 89, 145, 42, 20), несчастный номер.

Этот подход дает TLE, есть ли лучший метод ??

Диапазон составляет от 1 до 10 ^ 18.

1

c++combinations math number-theory numbers

Решение

Другие решения

#include <map>
#include <set>

bool happy(int number) {
static std::map<int, bool> cache;

std::set<int> cycle;
while (number != 1 && !cycle.count(number)) {
if (cache.count(number)) {
number = cache[number] ? 1 : 0;
break;
}
cycle.insert(number);
int newnumber = 0;
while (number > 0) {
int digit = number % 10;
newnumber += digit * digit;
number /= 10;
}
number = newnumber;
}
bool happiness = number == 1;
for (std::set<int>::const_iterator it = cycle.begin();
it != cycle.end(); it++)
cache[*it] = happiness;
return happiness;
}

#include <iostream>

int main() {
for (int i = 1; i < 10; i++)
if (!happy(i))
std::cout << i << std::endl;
return 0;
}

Выход:

Логика и большая часть кода взяты отсюда: https://tfetimes.com/c-happy-numbers/

0

Источник

Accepted Answer

Ваш диапазон от 1 до 10¹⁸. Это означает, что ваши номера имеют максимум 18 цифр.

Учтите, что максимальный квадрат цифры равен 9² = 81, после выполнения квадратно-цифровой суммы раз, максимальное число составляет 18 * 81 = 1458.

Так что одной квадрат-цифры-суммы плюс таблица соответствия ~ 1500 элементов должно быть достаточно.

Или две цифры в квадрате плюс таблица соответствия ~ 330 элементов:

static const bool unhappy[330] {
1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,
1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,
1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,
0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,
1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,
1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0
}

inline bool is_unhappy(uint64_t n) {
while (n >= 330) {
int r = 0;
while (n > 0) {
int d = n % 10;
r += d*d;
n /= 10;
}
n = r;
}

return unhappy[n];
}

4