Каким должен быть тип данных для чисел в диапазоне 10^10 - 10^11?

Question

Предположим, у меня есть следующий код для циклического перебора чисел следующим образом:

 int p;
 cin>>p;
 for(unsigned long long int i=3*pow(10,p);i<6*pow(10,p);i++){

              //some code goes here
 }

Теперь на основе определенных проверок условий мне нужно распечатать i между диапазонами: 3*pow(10,p)<= i <6*pow(10,p)

Код работает нормально upto p=8, тогда это становится довольно вялым, и компилятор, кажется, застревает для p=9,10,11 и далее. Я предполагаю, что проблема заключается в использовании правильного типа данных. Какой должен быть правильный тип данных для использования здесь?

Цель этого цикла - найти приличные числа между диапазонами. Достойные числа обозначаются следующим образом: 1) 3, 5 или обе цифры. Никакая другая цифра не допускается. 2) Количество появлений 3 делится на 5. 3) Количество появлений 5 делится на 3.

ПРИМЕЧАНИЕ: я использовал unsigned long long int Вот (0 to 18,446,744,073,709,551,615), Я работаю на 32-битной машине.

Answer 1

Вы могли бы использовать <cstdint> И его int64_t (который гарантированно имеет 64 бита), и вы должны вычислить мощность вне цикла; а также long long имеет как минимум 64 бита в последних стандартах C или C++.

Но, как упоминалось в комментарии 1201ProgramAlarm, циклы 3e11 (т.е. 300 миллиардов) - это много, даже на наших быстрых машинах. Это может занять минуты или часы: для элементарной операции требуется наносекунда (или половина). 3e9 операции требуют нескольких секунд; Операции 3е11 требуют нескольких минут. Ваше тело цикла может выполнять несколько тысяч (или даже больше) элементарных операций (например, инструкции машинного кода).

Это не компилятор, который застрял: компиляция вашего кода выполняется легко и быстро (при условии, что программа имеет разумный размер, например, менее десяти тысяч строк кода, без странных приемов препроцессора или расширений шаблонов, которые патологически расширяют их). Это компьютер, на котором работает скомпилированный исполняемый файл.

Если вы тестируете свой код, не забудьте включить оптимизацию в вашем компиляторе (например, компиляцию с g++ -Wall -O2 -arch=native при использовании GCC...)

Вы должны больше думать о своей проблеме и переформулировать ее, чтобы иметь меньшее пространство для поиска.

На самом деле, ваши приличные числа могут больше рассматриваться как последовательности цифр, представляющих их; в конце концов, число не имеет цифр (в частности, число, выраженное в двоичной или троичной системе счисления, не может иметь 3 как его цифра), только некоторые представления числа имеют цифры.

Тогда вы должны только рассмотреть строки 3 или же 5 которые короче 12 символов, и у вас их намного меньше (менее 10000 и, вероятно, менее 2 ^13, т.е. 8192); повторение десять тысяч раз должно быть быстрым. Так что генерируйте каждую строку меньше чем, например, 15 символов только 3 а также 5 в этом, и проверьте, если это прилично.