c - 欧拉+ #97 项目模块化指数不起作用

Question

我正在尝试解决来自Hackerrank的Project Euler+ #97。该问题要求计算A x B ** C + D的最后 12 位数字。我的尝试是使用来自维基百科的模块化幂模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("%012llun", (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和clang 8.1.0：

#include <stdio.h>
int main()
{
fprintf(stdout, "sizeof(unsigned long long) = %un", (unsigned) sizeof(unsigned long long));
fprintf(stdout, "sizeof(__uint128_t) = %un", (unsigned) sizeof(__uint128_t));
fprintf(stdout, "sizeof(long double) = %un", (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("%012llun", (unsigned long long) acc);
return 0;
}