nyoj28 大数阶乘亿进制优化-白红宇

nyoj28 大数阶乘亿进制优化

阅读量：4948 次

发布时间：2019-06-11

本文共 1039 字，大约阅读时间需要 3 分钟。

思路：刚开始用的十进制模拟手算加法，超时了。然后想到刘汝佳大哥书上面用的亿进制能够加速大数运算，果然180ms过掉了.

亿进制与十进制相同，只不过是把八位看做一位，例如6464654654165，看成亿进制就是64646,54654165，这样运算时可以同时计算八位，快了很多。当然，想更快可以使用更高的进制，但注意不要超出long long范围

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                
                  typedef long long LL;const int maxn = 1e4 + 5, base = 100000000;int res[maxn];int len;int main() { int n; while(scanf("%d", &n) == 1) { memset(res, 0, sizeof(res)); res[0] = 1; len = 1; for(int i = 2; i <= n; ++i) { int g = 0; for(int j = 0; j < len || g > 0; ++j) { LL x = (LL)i * res[j] + g; res[j] = (int)(x % base); g = int(x / base); //进位标记 len = max(j+1, len); //更新结果的长度 } } for(int i = len-1; i >= 0; --i) { if(i == len-1) printf("%d", res[i]); else printf("%08d", res[i]); } printf("\n"); } return 0;}

如有不当之处欢迎指出！

转载于:https://www.cnblogs.com/flyawayl/p/8305389.html

你可能感兴趣的文章