所以我应该找出 2^n(0<=n<=100) where n is the input. I found a method to handle large numbers but the program fails when n>64 的最后 10 位数字。任何有关如何处理此问题的线索将不胜感激。
#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;
}
您不需要需要担心“高”位，因为乘以
2unsigned long long#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^100010715086071862673209484250490600018105614048117055336074437503883703\ 51051124936122493198378815695858127594672917553146825187145285692314\ 04359845775746985748039345677748242309854210746050623711418779541821\ 53046474983581941267398767559165543946077062914571196477686542167660\ 429831652624386837205668069376
而
n = 1000其他人指出，这是一种
naive(n)[hi64][lo64]幸运的是，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);
}
下面使用字符串来执行乘法：
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
因为您收到的其他答案实际上并没有表明您做错了什么：
x = (x * x) % p;
您假设
x * xlong long intx0x100000000long long int要么：
您需要一种方法来精确地将两个任意 10 位数字相乘。结果可能有 20 位数字，并且可能无法容纳在
long long intunsigned long long int或者：
您需要避免将多个可能为 10 位的数字相乘。
您接受的答案选择简单的重复乘法
2假设您要找到 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
这就是使用
64-bit double precision floating pointint64uint64对于所有整数指数
[0, 1024) 2^expn % 10^10
or
2 ** expn % 10 ** 10
根本不需要任何循环、递归或大整数库。