c^d mod n 这个算法怎么实现 （用C++ ） 注意C^d可能会超过最大长度 所以需要别的算法
答案:3 悬赏:50 手机版
解决时间 2021-02-09 20:05
- 提问者网友：半生酒醒
- 2021-02-09 15:56
c^d mod n 这个算法怎么实现 （用C++ ） 注意C^d可能会超过最大长度 所以需要别的算法
最佳答案
- 五星知识达人网友：雾月
- 2021-02-09 17:31
只要n不是很大，可以用快速求幂的方法做
int mod_exp(int c,int d,int n)
{
long long res=1;
while(d){
if(d&1) res=res*c%n;
c=c*c%n;
d>>=1;
}
return res;
｝追问如果n比较大会怎么样？？追答计算机最多只能处理64位整数，也就是2^63-1,如果超过这个范围就得用高精度算法了
int mod_exp(int c,int d,int n)
{
long long res=1;
while(d){
if(d&1) res=res*c%n;
c=c*c%n;
d>>=1;
}
return res;
｝追问如果n比较大会怎么样？？追答计算机最多只能处理64位整数，也就是2^63-1,如果超过这个范围就得用高精度算法了
全部回答
- 1楼网友：慢性怪人
- 2021-02-09 20:11
我同意楼上的两位，就是这种按二分d的做法
- 2楼网友：山君与见山
- 2021-02-09 19:09
int mod_exp(int c, int d, int n)
{
int ans = 1;
while(d > 0)
{
if(d % 2 == 1) ans = (ans * c) % n;
c = (c * c) % n;
d /= 2;
}
return ans;
}
{
int ans = 1;
while(d > 0)
{
if(d % 2 == 1) ans = (ans * c) % n;
c = (c * c) % n;
d /= 2;
}
return ans;
}
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯