查找 2^n 的最后 10 位数字

Question

所以我应该找出 2^n(0<=n<=100) 的最后 10 位数字，其中 n 是输入。我找到了一种处理大数的方法，但当 n>64 时程序失败。任何有关如何处理此问题的线索都将不胜感激。

#include<stdio.h>
#include<math.h>


/* Iterative Function to calculate (x^y)%p in O(log y) */
int power(long long int x, long long int y, long long int p)
{
long long int res = 1; // Initialize result

x = x % p; // Update x if it is more than or
// equal to p

while (y > 0) {

    // If y is odd, multiply x with result
    if (y & 1)
        res = (res * x) % p;

    // y must be even now
    y = y >> 1; // y = y/2
    x = (x * x) % p;
}
return res;
}

// C function to print last 10 digits of a^b
void printLastDigits(long long int a,long long int b)
{    

long long int temp = pow(10,10);

// Calling modular exponentiation
temp = power(a, b, temp);

if (temp)
    printf("%d",temp);
}

int main()
{
long long int n;
scanf("%d",&n);
printLastDigits(2,n);
return 0;
}

Answer 1

您 不需要 担心 'high' 位，因为乘以 2 左移它们超出了您感兴趣的产品的下半部分的范围。只要确保您使用 unsigned long long 类型（至少 64 位）来保存足够宽的整数类型，例如，

#include <inttypes.h>
#include <stdio.h>

void low_digits (unsigned int n)
{
    unsigned long long base = 2, modulus = 10000000000ULL;

    for (unsigned int i = 1; i <= n; i++)
    {
        fprintf(stdout, "2^%u mod 10^10 = %llu\n", i, base);
        base = (base * 2) % modulus;
    }
}

你可以用 bignum 计算器测试 2^1000:

10715086071862673209484250490600018105614048117055336074437503883703\ 51051124936122493198378815695858127594672917553146825187145285692314\ 04359845775746985748039345677748242309854210746050623711418779541821\ 53046474983581941267398767559165543946077062914571196477686542167660\ 429831652624386837205668069376

而 n = 1000 以上产量：5668069376

其他人注意到，这是一种 naive 方法，并且 mod 平方幂对于 (n) 足够大的值要有效得多。不幸的是，这将需要超出无符号 64 位值范围的产品，因此除非您准备实施 [hi64][lo64] 多精度 mul / mod 操作，否则它可能超出范围你的任务。

幸运的是，gcc 和 clang 的更高版本确实提供了扩展的 128 位整数类型：

#include <inttypes.h>
#include <stdio.h>

void low_digits (unsigned int n)
{
    unsigned long long base = 2, modulus = 10000000000ULL;
    __extension__ unsigned __int128 u = 1, w = base;

    while (n != 0)
    {
        if ((n & 0x1) != 0)
            u = (u * w) % modulus; /* (mul-reduce) */

        if ((n >>= 1) != 0)
            w = (w * w) % modulus; /* (sqr-reduce) */
    }

    base = (unsigned long long) u;
    fprintf(stdout, "2^%u mod 10^10 = %llu\n", n, base);
}

Answer 2

下面使用字符串来执行乘法：

void lastdigits(char digits[11], int n)
{
    int i, j, x, carry;
    for (i=0; i<n;i++) {
        for (j=9, carry=0; j>=0; j--) {
            x= digits[j]-'0';
            x *= 2;
            x += carry;
            if (x>9) {carry= 1; x -= 10;}
            else carry= 0;
            digits[j]= x+'0';
        }
    }
}

void test(void)
{
    char digits[11];

    strcpy(digits,"0000000001");
    lastdigits(digits,10);
    printf("%s\n",digits);

    strcpy(digits,"0000000001");
    lastdigits(digits,20);
    printf("%s\n",digits);

    strcpy(digits,"0000000001");
    lastdigits(digits,100);
    printf("%s\n",digits);
}

输出：

0000001024
0001048576
6703205376

Answer 3

由于您收到的其他答案实际上并没有显示您做错了什么：

x = (x * x) % p;

您假设 x * x 仍然适合 long long int。但是如果x是0x100000000（4294967296，10位十进制数字）并且long long int是64位，那么它就不适合了。

或者：

您需要一种方法来准确地将两个任意 10 位数字相乘。结果可能有 20 位数字，可能不适合 long long int 甚至 unsigned long long int。这意味着您需要使用一些 bigint 库或自己实现类似的东西。

或：

您需要避免将多个可能为 10 位的数字相乘。

您接受的答案选择了 2 的简单重复乘法。现在这足以解决你的问题，但请注意，如果你想允许非常大的指数，这确实会显着增加复杂性。

Answer 4

假设您正在寻找 2^n 的最后一位，您只需要考虑最后一位并忽略其他所有数字

1. 2*2 = 4
2. 4*2 = 8
3. 8*2 = 16 (ignore last-but-one digit i.e 1)
4. 6*2 = 12 (ignore last-but-one digit i.e 1)
5. 2*2 = 4
6. 4*2 = 8
7. 8*2 = 16 (ignore last-but-one digit i.e 1)
8. 6*2 = 12 (ignore last-but-one digit i.e 1)
9. 2*2 = 4

... n-1 iterations

要查找 2^n 的最后 2 位数字，请忽略除最后 2 位数字之外的所有数字。

1. 2*2 = 4
2. 4*2 = 8
3. 8*2 = 16
4. 16*2 = 32
5. 32*2 = 64
6. 64*2 = 128 (Consider last 2 digits)
7. 28*2 = 56
8. 56*2 = 112 (Consider last 2 digits)
9. 12*2 = 24

... n-1 iterations

类似地，要找到 2^n 的最后 10 位数字，在每次迭代中只考虑最后 10 位数字并重复 n-1 次迭代。

注：

用这种方法，你在计算过程中得到的最大数字可以是 11 位数字 ~ 10^11，而对于 64 位机器，最大值是 ~ 2^64 = ~ 10^18

查找 2^n 的最后 10 位数字

Finding the last 10 digits of 2^n

c

unsigned-long-long-int