(a*b)%c 问题

时间：2023-03-09 04:48:22
(a*b)%c 问题

　

　　给你两个数__int64 类型的整数 a ，b，c。问你，(a*b)%c的值是多少？？我们知道: (a*b)%c = ((a%c)*(b%c))%c 。不过即使这样做，在c很大的情况下，(a%c)*(b%c)还是会越界。下面给出二进制的实现代码：

　　

 #include<cstdio>

 #include<cstring>

 using namespace std;

 __int64 Pow(__int64 a, __int64 b, __int64 c)

 {

     a %= c;

     b %= c;

     __int64 ret = ;   //计录(a*b)%c的值。

     while(b)

     {

         if(b&)

             ret += a, ret %= c;

         a <<= ; a %= c;  //a随着b中二进制位数而扩大每次扩大两倍。

         b >>= ;  //b来缩小两倍 去掉最后一位 由于当前最后一位我们用完了，

     }

     return ret;

 }

 int main()

 {

     __int64 a, b, c;

     while(~scanf("%I64d%I64d%I64d", &a, &b, &c))

     {

         printf("%I64d\n", Pow(a, b, c));

     }

     return ;

 }

随机推荐

  1. OpenCV——级联分类器（CascadeClassifier）

    级联分类器的计算特征值的基础类FeatureEvaluator 功能:读操作read.复制clone.获得特征类型getFeatureType,分配图片分配窗口的操作setImage.setWindo ...

  2. Ajax调用asp.net后台代码

    后台代码: [WebMethod] public static string CreateDate(string name,string age) { return "姓名:"+n ...

  3. php 序列化储存和转化 json_encode() json_decode($q,true)

    序列化是将变量转换为可保存或传输的字符串的过程:反序列化就是在适当的时候把这个字符串再转化成原来的变量使用.这两个过程结合起来,可以轻松地存储和传输数据,使程序更具维护性. 例如:当需要数据库只有一个 ...

  4. App Store审核指南中文版（2014.10.11更新）

    App Store审核指南中文版(2014.10.11更新) 2014-10-11 16:36 编辑: suiling 分类:AppStore研究 来源:CocoaChina  2 8657 App ...

  5. CloudStack添加新的API注意事项

    1.***Cmd上面的@APICommand里的responseObject关联对于的Response: 2.在tomcatconf/command.properties.in添加新API的权限: 3 ...

  6. ubuntu及终端快捷键

    1.关于终端的快捷键: Tab:tab键是比较常用的一个快捷键,它的作用是补全文件名或者路径.举例 来说,输入”cd /ho”在按一下tab键,终端里就会显示”cd /home”了.如果您的文件夹下, ...

  7. 解决PopupWindow遮住输入法

    1: PopupWindow中的设置 pop.setInputMethodMode(PopupWindow.INPUT_METHOD_NEEDED); pop.setSoftInputMode(Win ...

  8. Android AsyncTask 异步任务操作

    1:activity_main.xml <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/androi ...

  9. UESTC_Just a Maze CDOJ 1162

    Just a Maze Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 262144/262144KB (Java/Others) Su ...

  10. eclipse在ubuntu13.04下崩溃crash

    错误信息: # # A fatal error has been detected by the Java Runtime Environment: # # SIGSEGV (0xb) at pc=0 ...

相关文章