数据溢出的数学题，求指点
要求计算A的B的C次方次方，为了方便起见，把答案%1,000,000,007输出。输入3 4 5
输出763327764
说实话我有点懵，是我不理解题目的意思还是我写错代码，无论怎么算都算不出想要的结果。下面这个代码数据溢出，不知道怎么调，求指点。{:5_110:}
#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;
} long long换成double？ 不能懒 发表于 2021-9-15 21:14
long long换成double？
换成double报错， invalid operands of types 'double' and 'int' to binary 'operator%' 本帖最后由 jhq999 于 2021-9-16 21:02 编辑
无符号0xffffffffffffffff=18446744073709551615；
4的5次方1024
3的1024次方
1024位都表示不了
只能用数学方法
jhq999 发表于 2021-9-16 19:22
无符号0xffffffffffffffff=18446744073709551615；
4的5次方1024
3的1024次方
想知道什么代码能输出这个结果{:10_254:} 本帖最后由 jhq999 于 2021-9-16 22:36 编辑
a327904410 发表于 2021-9-16 22:07
想知道什么代码能输出这个结果
这么说吧，如果是2的1024次方结果至少需要128个字节保存，64位才8个字节 不能懒 发表于 2021-9-15 21:14
long long换成double？
longlong表示的整数范围比double大的多，因为都是64位，一个表示有符号整数，一个是有符号浮点。 本帖最后由 wp231957 于 2021-9-17 10:37 编辑
#include<stdio.h>
#include<math.h>
int main(){
long longa = 1000000007;
long longs = 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
*/ 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
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:25 编辑
人造人 发表于 2021-9-17 14:21
是 double 表示的范围比 long long 表示的范围大
虽然可以表示很大范围的数，但是表示的并不准确
感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算 jhq999 发表于 2021-9-17 15:18
感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算
这个我就不知道了，我不是数学系的，对数学了解不多
你看看 wp231957 的同余算法的那个代码，看看能不能看懂，我是看不懂，^_^
jhq999 发表于 2021-9-17 15:18
感觉得用数学方法简化计算，余数有什么定理或公式来简化计算？计算器能算
我突然想到了，是不是这个 计算器 程序也使用了和我一样的方法，使用了一些高精度的浮点运算库？
我觉得有可能，既然我可以轻松的使用 mpfr，我想 计算器 程序也完全可以使用这样的库
人造人 发表于 2021-9-17 15:42
这个我就不知道了，我不是数学系的，对数学了解不多
你看看 wp231957 的同余算法的那个代码，看看能不能 ...
有链接吗？自不量力一下{:5_109:} 人造人 发表于 2021-9-17 13:59
4 的 5 次方是 1024
3 的 1024 次方，这个数太大了，pow 函数的返回值类型是 double
就连 double 都无法 ...
是的，这个题目python很轻松跑出。感谢大佬解释那么多，我会好好消化这些内容的{:10_254:} wp231957 发表于 2021-9-17 10:34
这个易懂。。。。突然发现我数学太烂了{:10_277:} 本帖最后由 jhq999 于 2021-9-17 17:01 编辑
{:5_109:} {:5_109:} {:5_109:} {:5_109:}
#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，
*/ jhq999 发表于 2021-9-17 15:57
有链接吗？自不量力一下
^_^
人造人 发表于 2021-9-17 16:55
^_^
系统给四个数据评测，最后一个数据，123456789^987654321^135792468{:10_277:} 人造人 发表于 2021-9-17 16:55
^_^
评分系统太老，无法识别特殊库。我改用python看看能不能弄出来
页:
[1]
2