Question

C++求余数问题

const unsigned long long long_long_max=18446744073709551615;
const unsigned long long int_max=4294967296;

unsigned long long get(unsigned long long a,unsigned long long b,unsigned long long m)
{
a=a%m;
b=b%m;
unsigned long long A1,A2,B1,B2;
A1=a/int_max;
A2=a%int_max;
B1=b/int_max;
B2=b%int_max;
//将a*b拆分成(A1*2^32+A2)*(B1*2^32+B2)=(A1*B1)*(2^64-1+1)+(A1*B2+A2*B1)*2^32+A1*B1%m
unsigned long long result=(A1*B1)%m*(((long_long_max%m)+1)%m)+(A1*B2%m+A2*B1%m)%m*(int_max%m)%m+A2*B2%m;
//cout<<A1<<" "<<A2<<" "<<B1<<" "<<B2<<" "<<result%m<<endl;
return result%m;
}

为什么get(get(a,a,m),x0,m)和(get(get(a,x0,m),a,m))答案不一样??

Answer 1

代码没问题，应该输出也是对的。我注意到你的第二个(get(get(a,x0,m),a,m))，这个外面加了一个括号，没看到你的全部代码，你是不是用宏了？你带入的参数是long long型的吗？没有用double吧。

追问

没有 我把主要的算法写在上面了 下面只是运算而已。 double不够用。。

追答

你是怎么输出的。。。

追问

m=123456789012345678;
a=111111111111111111;
x0=333333333333333333;
cout<<"sadfs:"<<(get(get(a,x0,m),a,m))<<endl;//+get(a,c,m)+c)%m<<endl;

追答

你的get(get(a,a,m),x0,m)和(get(get(a,x0,m),a,m)种，作为参数的那两个，得出的结果可能越界了，你的返回值是unsigned long long 越界后，输出就改变了，导致执行最外面的get的时候，参数失真，致使不一样。

Answer 2

get函数中的三个参数都不同啊。
get(get(a,a,m),x0,m) 参数一是get(a,a,m),参数二是x0

get(get(a,x0,m),a,m)) 参数一是get(a,x0,m)，参数二是a

你这a,x0,m都相等吗？如果不相等的话，输出答案不一样就是对的吧。

追问

取余数运算？(a*a*x)%m 和(a%m)*(a%m)%m*(x0%m)%m 和 (a%m)*(x0%m)%m*(a%m)%m不一样么？？

追答

试了一个比较小的整数，结果是一样。

那还是参考那两位的答案吧，越界?

Answer 3

你有debug过没？这俩答案是一样的。。。。

追问

我都输出来过。。。就是不一样。。。我就是不知道。。我get()函数没问题吧

追答

你参数a，m，x0多是什么？我怎么debug就一样呢。

追问

a=18个1 m=123456789012345678 x0=18个3 如果运算过程了 A1=B1=0的话 答案是一样的 这个我验算过了 但是数字一旦很大接近了long long max就不行了

追答

你有检查你操作过程中譬如B1*2^32有没有溢出么？如果溢出了那肯定就有问题了。基本没见过你这么写程序的，不知你的目的为何。

追问

没有 我用的是unsigned long long 用VS2010编译的 可以取到2^64-1