`

【快速幂取模】fzu 1752 A^B mod C

阅读更多
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
1
1
分享到:
评论

相关推荐

    fzu online judge

    【fzu在线评测系统】是面向编程爱好者和学习者的一个平台,主要功能是提供各种算法题目供用户在线解答,以提升编程能力和算法思维。在这个压缩包文件中,包含的是一些关于fzu在线评测系统的解题记录,虽然题目难度...

    fzu 1698解题报告

    求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊

    福大fzu OJ题目

    不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)

    2021FZU计算机视觉期末复习

    空间域增强直接对像素值进行操作,如点运算、对数变换、幂次变换、对比拉伸和直方图均衡化等。频率域增强则是通过修改图像的傅立叶变换来实现。 空间滤波器在图像增强中扮演着重要角色,主要包括平滑空间滤波器和...

    ACM数学_FZU绝密资料

    - **标准方程**:椭圆的一般方程是 \(\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1\),其中 \(a\) 和 \(b\) 分别是椭圆的半长轴和半短轴长度。 #### 抛物线 - **标准方程**:抛物线的一般方程为 \(y^2 = 2px\),\(p\) ...

    fzu大数据基础实验4

    fzu大数据基础实验4

    2021FZU计算机视觉作业(八)

    在计算机视觉领域中,灰度共生矩阵(GLCM)是一种用于纹理特征分析的技术。它通过计算图像中像素值的相对位置和分布来揭示图像的纹理特性,这些特性在图像分割、特征提取和图像分析等领域中非常有用。...

    FZU飞跃手册 相关文件 (FZU Flying Book Relevant documents)

    (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 ...

    2011 ACM 多校联合 2011 MU11 13 FZU

    【标题】"2011 ACM 多校联合 2011 MU11 13 FZU" 指的是一项编程竞赛,ACM(国际计算机学会)每年都会举办多场这样的竞赛,旨在提升学生的算法设计和编程能力。ACM竞赛通常包括一系列的编程题目,参赛队伍需要在限定...

    FZU软件工程web课程复习资料-整理

    "FZU软件工程web课程复习资料-整理" 本资源是FZU软件工程web课程的复习资料,涵盖了web开发的基础知识和技术。下面是对该资源中所涉及的知识点的详细解释: 第一讲 web 开发概述 1. 因特网与万维网 因特网是一种...

    ACM半数集(FZU ACM上的半数集问题)

    FZU ACM 上的半数集问题 的源代码

    FZU2021计算机视觉慕课答案(一)

    FZU2021计算机视觉慕课是一门面向学生和研究人员的基础课程,其中包含了丰富的实践案例和练习题。从提供的文件内容中,我们可以提取一些计算机视觉中的基础知识点,包括图像的读取、显示、转换、保存、以及图像处理...

    FZU软件工程操作系统课程复习资料-整理

    FZU软件工程操作系统课程复习资料-整理 本资源摘要信息是关于FZU软件工程操作系统课程复习资料的整理,涵盖操作系统的基本概念、进程和线程、存储管理和文件系统等方面的知识点。 一、操作系统的定义和主要功能 ...

    C#作业(FZU)miniword完整版

    【C# miniword 完整版】是一款基于C#编程语言开发的小型文字处理软件,类似于微软的Word,主要用于FZU(福州大学)的教学与作业。该项目旨在让学生熟悉C#编程环境,掌握Windows Forms应用程序的开发技术,以及对文本...

    fzu 1812 coin 背包

    1812 coin 解题代码 多重背包的应用

    fzu—java张苏老师课件

    《fzu—java张苏老师课件》是一个针对Java初学者的课程资料集合,由一系列PPT文件组成,包括了从基础到进阶的多个章节。这个资源旨在帮助初学者系统地学习Java编程语言,逐步掌握其核心概念和技术。下面我们将详细...

    FZU2021计算机视觉答案(四)

    FZU2021计算机视觉答案(四)中包含了肤色检测的实验过程和代码实现,以下是从该文件中提取出来的知识点: 1. **肤色检测的基本原理**: 肤色检测通常基于色彩空间中的色度或亮度属性,例如,在RGB色彩空间中,...

    2021FZU计算机视觉答案(五)

    标题“2021FZU计算机视觉答案(五)”表明本文档是一份关于计算机视觉题目的解答集,特别是涉及到与图像处理和分析相关的内容。从给出的部分内容来看,文档包含实现特定图像处理任务的Python代码示例,具体涉及到...

    FZU编译原理实践作业一参考代码

    仅作参考,抄被发现后果自负哈。

Global site tag (gtag.js) - Google Analytics