KIDx 的解题报告
参考《算法艺术与信息学竞赛》:
题目:http://acm.fzu.edu.cn/problem.php?pid=1752
由于(1<=A,B,C<2^63),所以要用到mul_mod二分求a*a,不然会溢出
原来的快速幂取模简单模板:
//求(a^b)%c
int qmod (int a, int b, int c)
{
int res = 1;
for ( ; b; b >>= 1)
{
if (b & 1)
res = (LL)res * a % c;
a = (LL)a * a % c;
}
return res;
}
对于fzu 1752这题:
速度就这鬼样:
#include <iostream>
using namespace std;
#define ULL unsigned __int64
ULL mul_mod (ULL a, ULL b, ULL c) //利用快速取幂模的思想求a*a%c和res*a%c,为了防止溢出
{
ULL res = 0;
for ( ; b; b >>= 1)
{
if (b & 1)
{
res += a; //这两句换成 res = (res + a) % c 会很慢
if (res >= c) res -= c;
}
a <<= 1; //这两句换成 a = (a + a) % c 也很慢
if (a >= c) a -= c;
}
return res;
}
ULL qmod (ULL a, ULL b, ULL c)
{
ULL res = 1;
for ( ; b; b >>= 1)
{
if (b & 1)
res = mul_mod (a, res, c);
a = mul_mod (a, a, c);
}
return res;
}
int main()
{
ULL a, b, c;
while (~scanf ("%I64u%I64u%I64u", &a, &b, &c))
printf ("%I64u\n", qmod (a%c, b, c));
return 0;
}
- 大小: 104.9 KB
- 大小: 8.2 KB
分享到:
相关推荐
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
2021FZU计算机视觉作业(八)
2021FZU计算机视觉期末复习
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
fzu大数据基础实验4
(This is a collection of documents relating to our Leapfrog Handbook project, including member grouping information forms, task summary documents for each group member, a project diary, and other ...
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
FZU ACM 上的半数集问题 的源代码
FZU2021计算机视觉答案(三)
FZU2021计算机视觉答案(四)
2021FZU计算机视觉答案(五)
2021FZU计算机视觉答案(二 )
2021FZU计算机视觉答案(六)
2011 ACM 多校联合 2011 MU11 13 FZU