c++ - 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在最新的 C 或 C++ 标准中至少有 64 位。

但是，正如 1201ProgramAlarm 的评论中提到的那样, 3e11(即 3000 亿)循环很多，即使在我们的快速机器上也是如此。这可能需要几分钟或几小时:基本操作需要一纳秒(或一半)。 3e9 操作需要几秒钟； 3e11 操作需要几分钟。您的循环体可以执行数千(甚至更多)基本操作(即 machine code 指令)。

卡住的不是编译器:编译代码简单快捷(只要程序大小合理，例如少于一万行代码，没有怪异的预处理器或模板扩展技巧病态地扩展它们) .它是运行编译后的可执行文件的计算机。

如果您对代码进行基准测试，请不要忘记启用 optimizations在您的编译器中(例如，如果使用 GCC 则使用 g++ -Wall -O2 -arch=native 编译 ...)

您应该对您的问题进行更多思考 并重新制定它以使其具有更小的 search space .

实际上，您的体面数字可能更像是代表它们的数字串；毕竟，number没有数字(特别是用二进制或三元表示法表示的数字不能有 3 作为它的数字)，只有数字的某些表示有数字。

那你应该只考虑3的字符串或 5短于 12 个字符，而且你的字符少得多(少于 10000，可能少于 2¹³ 即 8192)；迭代一万次应该很快。因此，生成小于例如的每个字符串15 个字符只有 3和 5在其中，并测试它是否像样。