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

a327904410 · 发表于 2021-9-15 20:41:14

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

要求计算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

本帖最后由 wp231957 于 2021-9-17 10:37 编辑

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

int main(){
        long long  a = 1000000007;
        long long  s = 1;
        int m=1024;
        while (m>0){
            if ( s < a ) {
                s*=3;
                m-=1;
            } 
            else{
               s %= a;
            }  
        }
        printf("同余结果：%lld\n",s); 
        return 0;
}

/*
PS D:\我> ./wp4
   同余结果：763327764
*/

跳转到最佳答案楼层

不能懒 · 发表于 2021-9-15 21:14:12

long long换成double？

a327904410 · 发表于 2021-9-15 21:30:18

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

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

jhq999 · 发表于 2021-9-16 19:22:51

本帖最后由 jhq999 于 2021-9-16 21:02 编辑

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

a327904410 · 发表于 2021-9-16 22:07:58

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

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

jhq999 · 发表于 2021-9-16 22:28:07

本帖最后由 jhq999 于 2021-9-16 22:36 编辑

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

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

jhq999 · 发表于 2021-9-16 22:34:39

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

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

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

这个最佳答案由 wp231957 给出，感谢 wp231957 的回答。

单击隐藏图章

本帖最后由 wp231957 于 2021-9-17 10:37 编辑

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

int main(){
        long long  a = 1000000007;
        long long  s = 1;
        int m=1024;
        while (m>0){
            if ( s < a ) {
                s*=3;
                m-=1;
            } 
            else{
               s %= a;
            }  
        }
        printf("同余结果：%lld\n",s); 
        return 0;
}

/*
PS D:\我> ./wp4
   同余结果：763327764
*/

人造人 · 发表于 2021-9-17 13:59:51

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

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

int main(void) {
    int a = 3, b = 4, c = 5;
    long double n = 1000000007.0L;
    long double x = powl(a, powl(b, c));
    long double z = fmodl(x, n);
    printf("sizeof(long double): %lu\n", sizeof(long double));
    printf("a^(b^c)%%%Lf: %Lf\n", n, z);
    return 0;
}

/*
$ ./main
sizeof(long double): 16
a^(b^c)%1000000007.000000: 650342243.000000
$
*/

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

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

int main(void) {
    int a = 3, b = 4, c = 5;
    //long double n = 1000000007.0L;
    long double x = powl(a, powl(b, c));
    //long double z = fmodl(x, n);
    //printf("sizeof(long double): %lu\n", sizeof(long double));
    //printf("a^(b^c)%%%Lf: %Lf\n", n, z);
    printf("a^(b^c): %Lf\n", x);
    return 0;
}

/*
$ ./main
a^(b^c): 373391848741020043440934059606603790515058800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.000000
$
*/

我用数学的方法算过了，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 库

The Multiple Precision Floating-Point Reliable Library

google 翻译

多精度浮点可靠库

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

#include <stdio.h>
#include <mpfr.h>

int main(void) {
    mpfr_t n, a, b, c, z;
    mpfr_inits2(8192, n, a, b, c, z, NULL);
    mpfr_set_str(n, "1000000007", 10, MPFR_RNDD);
    mpfr_inp_str(a, stdin, 10, MPFR_RNDD);
    mpfr_inp_str(b, stdin, 10, MPFR_RNDD);
    mpfr_inp_str(c, stdin, 10, MPFR_RNDD);
    mpfr_pow(z, b, c, MPFR_RNDD);
    mpfr_pow(z, a, z, MPFR_RNDD);
    mpfr_fmod(z, z, n, MPFR_RNDD);
    mpfr_printf("%.0Rf\n", z);
    mpfr_clears(n, a, b, c, z, NULL);
    mpfr_free_cache();
    return 0;
}

编译运行

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

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

人造人 · 发表于 2021-9-17 14:21:09

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

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

#include <stdio.h>

int main(void) {
    unsigned long long a = 18446744073709551615LLU;
    unsigned long long b = 118446744073709551615LLU;
    double x = 18446744073709551615.0L;
    double y = 118446744073709551615.0L;
    printf("%Lu\n", a);
    printf("%Lu\n", b);
    printf("%f\n", x);
    printf("%f\n", y);
    return 0;
}

$ ./main
18446744073709551615
7766279631452241919
18446744073709551616.000000
118446744073709551616.000000
$

jhq999 · 发表于 2021-9-17 15:18:06

本帖最后由 jhq999 于 2021-9-17 15:25 编辑

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

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

人造人 · 发表于 2021-9-17 15:42:45

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

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

人造人 · 发表于 2021-9-17 15:46:20

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

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

jhq999 · 发表于 2021-9-17 15:57:37

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

有链接吗？自不量力一下

a327904410 · 发表于 2021-9-17 16:51:46

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

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

a327904410 · 发表于 2021-9-17 16:53:35

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

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

jhq999 · 发表于 2021-9-17 16:55:00

本帖最后由 jhq999 于 2021-9-17 17:01 编辑

#define CUSU 1000000007
int main()
{
        unsigned __int64 a=0,c=1,t=3;//1000000007
        for (int i = 0; i < 1024; i++)
        {
                        a=t%CUSU;
                        c*=a;
                        while (c>CUSU)
                        {
                                c%=CUSU;
                        }
                        
                
        }
        printf("%I64u",c);
        
        return 0;


}
//我用的是3、乘法律
/*
1、加法律：(a+b) mod c = ((a mod c) + (b mod c)) mod c。

2、减法律：(a-b) mod c = ((a mod c) - (b mod c)) mod c。

3、乘法律：(a*b) mod c = ((a mod c) * (b mod c)) mod c。

4、次方律：。

5、消去律：若 gcd(c,p) = 1，
*/

人造人 · 发表于 2021-9-17 16:55:10

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

^_^

a327904410 · 发表于 2021-9-17 17:58:59

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

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

a327904410 · 发表于 2021-9-17 18:08:49

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

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

账号		自动登录	找回密码
密码			立即注册