[已解决]数据溢出的数学题，求指点

a327904410

要求计算A的B的C次方次方，为了方便起见，把答案%1,000,000,007输出。
输入3 4 5
输出763327764

说实话我有点懵，是我不理解题目的意思还是我写错代码，无论怎么算都算不出想要的结果。下面这个代码数据溢出，不知道怎么调，求指点。

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

int main(){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        long long sum;
        sum = ((long long)pow(a, pow(b, c))) % 1000000007;
        printf("%llu", sum);
        return 0;
}

最佳答案

月排行榜 / 总排行榜

wp231957

2021-9-17 10:34:39

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. int main(){
   
5.         long long  a = 1000000007;
   
6.         long long  s = 1;
   
7.         int m=1024;
   
8.         while (m>0){
   
9.             if ( s < a ) {
   
10.                 s*=3;
    
11.                 m-=1;
    
12.             }
    
13.             else{
    
14.                s %= a;
    
15.             }  
    
16.         }
    
17.         printf("同余结果：%lld\n",s);
    
18.         return 0;
    
19. }
    
20. 
    
21. /*
    
22. PS D:\我> ./wp4
    
23.    同余结果：763327764
    
24. */

复制代码

跳转到最佳答案楼层

不能懒

long long换成double？

a327904410

不能懒 发表于 2021-9-15 21:14
long long换成double？

换成double报错，[Error] invalid operands of types 'double' and 'int' to binary 'operator%'

jhq999

无符号0xffffffffffffffff=18446744073709551615；
4的5次方1024
3的1024次方
1024位都表示不了
只能用数学方法

a327904410

jhq999 发表于 2021-9-16 19:22
无符号0xffffffffffffffff=18446744073709551615；
4的5次方1024
3的1024次方

想知道什么代码能输出这个结果

jhq999

a327904410 发表于 2021-9-16 22:07
想知道什么代码能输出这个结果

这么说吧，如果是2的1024次方结果至少需要128个字节保存，64位才8个字节

jhq999

不能懒 发表于 2021-9-15 21:14
long long换成double？

longlong表示的整数范围比double大的多，因为都是64位，一个表示有符号整数，一个是有符号浮点。

wp231957

1. #include<stdio.h>
   
2. #include<math.h>
   
3. 
   
4. int main(){
   
5.         long long  a = 1000000007;
   
6.         long long  s = 1;
   
7.         int m=1024;
   
8.         while (m>0){
   
9.             if ( s < a ) {
   
10.                 s*=3;
    
11.                 m-=1;
    
12.             }
    
13.             else{
    
14.                s %= a;
    
15.             }  
    
16.         }
    
17.         printf("同余结果：%lld\n",s);
    
18.         return 0;
    
19. }
    
20. 
    
21. /*
    
22. PS D:\我> ./wp4
    
23.    同余结果：763327764
    
24. */

复制代码

人造人

4 的 5 次方是 1024
3 的 1024 次方，这个数太大了，pow 函数的返回值类型是 double
就连 double 都无法表示 3 的 1024 次方，你强制转换成 long long 就更无法表示了
还有，就算是使用 long double，16 个字节，128 bit，计算出的结果也是不对的

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main(void) {
   
5.     int a = 3, b = 4, c = 5;
   
6.     long double n = 1000000007.0L;
   
7.     long double x = powl(a, powl(b, c));
   
8.     long double z = fmodl(x, n);
   
9.     printf("sizeof(long double): %lu\n", sizeof(long double));
   
10.     printf("a^(b^c)%%%Lf: %Lf\n", n, z);
    
11.     return 0;
    
12. }
    
13. 
    
14. /*
    
15. $ ./main
    
16. sizeof(long double): 16
    
17. a^(b^c)%1000000007.000000: 650342243.000000
    
18. $
    
19. */

复制代码

输出的结果不对，是因为 3 的 1024 次方 算的不准确

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int main(void) {
   
5.     int a = 3, b = 4, c = 5;
   
6.     //long double n = 1000000007.0L;
   
7.     long double x = powl(a, powl(b, c));
   
8.     //long double z = fmodl(x, n);
   
9.     //printf("sizeof(long double): %lu\n", sizeof(long double));
   
10.     //printf("a^(b^c)%%%Lf: %Lf\n", n, z);
    
11.     printf("a^(b^c): %Lf\n", x);
    
12.     return 0;
    
13. }
    
14. 
    
15. /*
    
16. $ ./main
    
17. a^(b^c): 373391848741020043440934059606603790515058800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000
    
18. $
    
19. */

复制代码

我用数学的方法算过了，3 的 1024 次方的个位数字是 1，不是 0，不是其他，是 1


3 的 1 次方 的个位数字是 3
3 的 2 次方 的个位数字是 9
3 的 3 次方 的个位数字是 7
3 的 4 次方 的个位数字是 1
3 的 5 次方 的个位数字是 3
。。。

3 9 7 1 一循环
指数 1 对应 3
指数 2 对应 9
指数 3 对应 7
指数 4 对应 1

(n - 1) % 4 就是 3 的 n 次方 的个位数字 的索引，用来索引 3 9 7 1
0 -> 3
1 -> 9
2 -> 7
3 -> 1

(1024 - 1) % 4 = 3
3 -> 1
所以 3 的 1024 次方的个位数字是 1

我用 python 算了一下，居然正确，这是道 python 题吧，^_^


既然 C语言中的 long double 都算不了，怎么办？
我百度找到了个好东西，gnu 的 mpfr 库

1. The Multiple Precision Floating-Point Reliable Library

复制代码

google 翻译

1. 多精度浮点可靠库

复制代码

官方文档：https://www.mpfr.org/mpfr-4.0.1/mpfr.pdf

1. #include <stdio.h>
   
2. #include <mpfr.h>
   
3. 
   
4. int main(void) {
   
5.     mpfr_t n, a, b, c, z;
   
6.     mpfr_inits2(8192, n, a, b, c, z, NULL);
   
7.     mpfr_set_str(n, "1000000007", 10, MPFR_RNDD);
   
8.     mpfr_inp_str(a, stdin, 10, MPFR_RNDD);
   
9.     mpfr_inp_str(b, stdin, 10, MPFR_RNDD);
   
10.     mpfr_inp_str(c, stdin, 10, MPFR_RNDD);
    
11.     mpfr_pow(z, b, c, MPFR_RNDD);
    
12.     mpfr_pow(z, a, z, MPFR_RNDD);
    
13.     mpfr_fmod(z, z, n, MPFR_RNDD);
    
14.     mpfr_printf("%.0Rf\n", z);
    
15.     mpfr_clears(n, a, b, c, z, NULL);
    
16.     mpfr_free_cache();
    
17.     return 0;
    
18. }
    

复制代码

编译运行

1. $ gcc -g -Wall -o main main.c -lmpfr
   
2. $ ./main
   
3. 3 4 5
   
4. 763327764
   
5. $
   

复制代码

python 估计也是使用了类似的库，要我猜的话，很有可能就是 mpfr

人造人

jhq999 发表于 2021-9-16 22:34
longlong表示的整数范围比double大的多，因为都是64位，一个表示有符号整数，一个是有符号浮点。

是 double 表示的范围比 long long 表示的范围大
虽然可以表示很大范围的数，但是表示的并不准确

1. #include <stdio.h>
   
2. 
   
3. int main(void) {
   
4.     unsigned long long a = 18446744073709551615LLU;
   
5.     unsigned long long b = 118446744073709551615LLU;
   
6.     double x = 18446744073709551615.0L;
   
7.     double y = 118446744073709551615.0L;
   
8.     printf("%Lu\n", a);
   
9.     printf("%Lu\n", b);
   
10.     printf("%f\n", x);
    
11.     printf("%f\n", y);
    
12.     return 0;
    
13. }
    

复制代码

1. $ ./main
   
2. 18446744073709551615
   
3. 7766279631452241919
   
4. 18446744073709551616.000000
   
5. 118446744073709551616.000000
   
6. $

复制代码

jhq999

人造人 发表于 2021-9-17 14:21
是 double 表示的范围比 long long 表示的范围大
虽然可以表示很大范围的数，但是表示的并不准确

感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算

人造人

jhq999 发表于 2021-9-17 15:18
感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算

这个我就不知道了，我不是数学系的，对数学了解不多
你看看 wp231957 的同余算法的那个代码，看看能不能看懂，我是看不懂，^_^

人造人

jhq999 发表于 2021-9-17 15:18
感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算

我突然想到了，是不是这个 计算器 程序也使用了和我一样的方法，使用了一些高精度的浮点运算库？
我觉得有可能，既然我可以轻松的使用 mpfr，我想 计算器 程序也完全可以使用这样的库

jhq999

人造人 发表于 2021-9-17 15:42
这个我就不知道了，我不是数学系的，对数学了解不多
你看看 wp231957 的同余算法的那个代码，看看能不能 ...

有链接吗？自不量力一下

a327904410

人造人 发表于 2021-9-17 13:59
4 的 5 次方是 1024
3 的 1024 次方，这个数太大了，pow 函数的返回值类型是 double
就连 double 都无法 ...

是的，这个题目python很轻松跑出。感谢大佬解释那么多，我会好好消化这些内容的

a327904410

wp231957 发表于 2021-9-17 10:34

这个易懂。。。。突然发现我数学太烂了

jhq999

1. #define CUSU 1000000007
   
2. int main()
   
3. {
   
4.         unsigned __int64 a=0,c=1,t=3;//1000000007
   
5.         for (int i = 0; i < 1024; i++)
   
6.         {
   
7.                         a=t%CUSU;
   
8.                         c*=a;
   
9.                         while (c>CUSU)
   
10.                         {
    
11.                                 c%=CUSU;
    
12.                         }
    
13.                        
    
14.                
    
15.         }
    
16.         printf("%I64u",c);
    
17.        
    
18.         return 0;
    
19. 
    
20. 
    
21. }
    
22. //我用的是3、乘法律
    
23. /*
    
24. 1、加法律：(a+b) mod c = ((a mod c) + (b mod c)) mod c。
    
25. 
    
26. 2、减法律：(a-b) mod c = ((a mod c) - (b mod c)) mod c。
    
27. 
    
28. 3、乘法律：(a*b) mod c = ((a mod c) * (b mod c)) mod c。
    
29. 
    
30. 4、次方律：。
    
31. 
    
32. 5、消去律：若 gcd(c,p) = 1，
    
33. */

复制代码

人造人

jhq999 发表于 2021-9-17 15:57
有链接吗？自不量力一下

^_^

a327904410

人造人 发表于 2021-9-17 16:55
^_^

系统给四个数据评测，最后一个数据，123456789^987654321^135792468

a327904410

人造人 发表于 2021-9-17 16:55
^_^

评分系统太老，无法识别特殊库。我改用python看看能不能弄出来