项目欧拉+＃97模块指数不起作用

Question

我想从Hackerrank解决Project Euler+ #97。该问题要求计算A x B ** C + D的最后12位数字。我尝试使用来自Wikipedia的模幂运算mod 10 ** 12以有效计算最后12位数字并避免溢出。但是，除了样本2 x 3 ** 4 + 5之外的所有情况，我都会出错。根据约束条件，unsigned long long不应该溢出。

---

问题：

现在，我们要学习如何计算这样的大数目的一些最后的数字。假设我们有很多数字A x B ** C + D，我们想知道这些数字的最后12位数字。

约束：

• 1≤：T≤500000
• 1≤A，B，C，d≤10 ** 9

输入：第一行包含一个整数T - 测试次数。 T行跟随每个包含4个整数（A，B，C和D）。

输出：输出恰好一行包含正好12位数字 - 所有结果总和的最后12位数字。如果总和小于10 ** 12那么打印相应数量的前导零。

---

我用C尝试

#include <stdio.h> 

int main() { 
    const unsigned long long limit = 1000000000000; 
    int cases; 
    for (scanf("%d", &cases); cases; --cases) { 
     // mult = A, base = B, exp = C, add = D 
     unsigned long long mult, base, exp, add; 
     scanf("%llu %llu %llu %llu", &mult, &base, &exp, &add); 
     base = base % limit; 
     while (exp) { 
      if (exp & 1) { 
       mult = (mult * base) % limit; 
      } 
      exp >>= 1; 
      base = (base * base) % limit; 
     } 
     printf("%012llu\n", (mult + add) % limit); 
    } 
    return 0; 
} 

Answer 1

我想你可能会溢出无符号很长很长的数学（如 - 模2^64），因为你在你的内部循环基础的计算可以得到高达（ 10^12 - 1）^ 2 = 10^24 = 2^79.726，远远超过2^64。例如，想想B = 10^6 - 1和C = 4

在我的MacBook Pro运行的64B版本的Mac OS X的铿锵8.1.0：

#include <stdio.h> 

int main() 
{ 
    fprintf(stdout, "sizeof(unsigned long long) = %u\n", (unsigned) sizeof(unsigned long long)); 
    fprintf(stdout, "sizeof(__uint128_t) = %u\n", (unsigned) sizeof(__uint128_t)); 
    fprintf(stdout, "sizeof(long double) = %u\n", (unsigned) sizeof(long double)); 

    return 0; 
} 

说：

sizeof(unsigned long long) = 8 
sizeof(__uint128_t) = 16 
sizeof(long double) = 16 

如果您的平台长16或10而不是长久，那么我认为您是清楚的。如果它像我的那样说8，那么你需要重做你的答案，或者强制128b（或80b）整数数学或者模仿它。

您可以尝试__uint128_t，它受gcc和clang支持。否则，你需要使用像long double和fmodl（）这样的函数，它可能有足够的尾数位，但可能不会像你想要的那样给出确切的答案。

另外，您不会像任务说的那样累积多个结果。这是我的拍摄，根据你的程序，但使用__uint128_t。

#include <stdio.h> 
#include <stdlib.h> 

#define BILLION  1000000000 
#define TRILLION 1000000000000 

int main() 
{ 
    const __uint128_t limit = TRILLION; 
    unsigned long  cases = 0; 
    __uint128_t  acc = 0; 

    if (scanf("%lu", &cases) != 1 || cases == 0 || cases > 500000) 
    abort(); 

    while (cases-- > 0) 
    {    
    unsigned long a, b, c, d; 
    __uint128_t b2c = 1, bbase; 

    if (scanf("%lu %lu %lu %lu", &a, &b, &c, &d) != 4 || 
     a == 0 || a > BILLION || b == 0 || b > BILLION || 
     c == 0 || c > BILLION || d == 0 || d > BILLION) 
     abort(); 

    for (bbase = b; c > 0; c >>= 1) 
    { 
     if ((c & 0x1) != 0) 
     b2c = (b2c * bbase) % limit; // 64b overflow: ~10^12 * ~10^12 ~= 10^24 > 2^64 

     bbase = (bbase * bbase) % limit; // same overflow issue as above 
    } 

    // can do modulus on acc only once at end of program instead because 
    // 5 * 10^5 * (10^9 * (10^12 - 1) + 10^9) = 5 * 10^26 < 2^128 

    acc += a * b2c + d; 
    } 

    acc %= limit; 

    printf("%012llu\n", (unsigned long long) acc); 

    return 0; 
}