首页 > 代码库 > (a*b)%c 问题
(a*b)%c 问题
给你两个数__int64 类型的整数 a ，b，c。问你，(a*b)%c的值是多少？？我们知道: (a*b)%c = ((a%c)*(b%c))%c 。不过即使这样做，在c很大的情况下，(a%c)*(b%c)还是会越界。下面给出二进制的实现代码：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 5 __int64 Pow(__int64 a, __int64 b, __int64 c) 6 { 7 a %= c; 8 b %= c; 9 __int64 ret = 0; //计录(a*b)%c的值。10 while(b)11 {12 if(b&1)13 ret += a, ret %= c;14 a <<= 1; a %= c; //a随着b中二进制位数而扩大每次扩大两倍。15 b >>= 1; //b来缩小两倍 去掉最后一位 由于当前最后一位我们用完了，16 }17 return ret;18 }19 20 int main()21 {22 __int64 a, b, c;23 while(~scanf("%I64d%I64d%I64d", &a, &b, &c))24 {25 printf("%I64d\n", Pow(a, b, c));26 }27 return 0;28 }
(a*b)%c 问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。