`

【高次幂取模的应用】HDU 3609 Up-up

阅读更多
KIDx 的解题报告
题目很容易看懂:http://acm.hdu.edu.cn/showproblem.php?pid=3609

降幂公式:

这速度可以排到前10了:

#include <iostream>
using namespace std;
#define LL unsigned __int64
#define M 205

int phi[M];

int Euler (int n)    //求n的欧拉值
{
	int i, res = n;
	for (i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			res = res - res/i;
			while (n % i == 0)
				n /= i;
		}
	}
	if (n > 1)
		res = res - res/n;
	return res;
}

LL qmod (LL a, LL b, int c)    //快速幂取模
{
	LL res = 1;
	for ( ; b; b >>= 1)
	{
		if (b & 1)
			res = res * a % c;
		a = a * a % c;
	}
	return res;
}

LL isok (LL a, LL b, int c)    //目的是判断a^b是否>=c
{
	LL res = 1, i;
	for (i = 0; i < b; i++)
	{
		res *= a;
		if (res >= c)
			return res;
	}
	return res;
}

LL upup (LL a, int k, int num)    //按照题意递归地使用公式
{
	if (phi[num] == 1) return 1;    //显然符合公式条件,很容易套公式知道是1,这实际上是剪枝
	if (k == 1) return a % phi[num];//返回上一层的a的幂
	LL b = upup (a, k-1, num+1);    //得到a的幂b
	LL x = isok (a, b, phi[num]);
	if (x >= phi[num])    //使用公式的条件,满足条件可以进行降幂,返回的是上层a的幂
		return qmod (a % phi[num], b, phi[num]) + phi[num];
	else return x;    //不使用公式,直接返回a^b,也属于上层a的幂
}

int main()
{
	LL a;
	int k;
	phi[0] = 100000000;
	for (k = 1; k < M; k++)
		phi[k] = Euler (phi[k-1]);    //预处理所需欧拉值
	while (~scanf ("%I64u%d", &a, &k))
	{
		printf ("%I64u\n", upup (a, k, 0) % phi[0]);
	}
    return 0;
}
  • 大小: 8.2 KB
  • 大小: 12.1 KB
1
1
分享到:
评论

相关推荐

    HDU-EID-V2-核心板1

    在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...

    HDU+2000-2099+解题报告

    这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、答案以及解题思路,对于学习算法和提升编程能力具有很高的价值。 在这个范围内,我们可以预见到涵盖的算法类型可能包括但不限于:...

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo.zip

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    HDU-2000-2099.rar_hdu

    这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些题目涵盖了初级到高级的各种算法,对于学习和提升编程技能非常有帮助。 首先,我们来看看这些题目可能涉及到的基础知识...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    2019-hdu-multi-(2019杭电多校第二场数据与标程).zip

    《2019-hdu-multi-(2019杭电多校第二场数据与标程).zip》是一个专门针对编程竞赛爱好者和ACM(国际大学生程序设计竞赛)参赛者的资源包。这个压缩文件的核心内容是2019年杭州电子科技大学(HDU)主办的多校联合...

    HDU-1535-.zip_多源点

    标题中的"HDU-1535-.zip_多源点"表明这是一个关于解决 ACM (国际大学生程序设计竞赛)问题的程序代码包,问题编号为 HDU 1535,且该问题涉及到多源点的最短路径计算。描述中提到的"求多源点到单终点的最短路(反向...

    HDU-EID-V2-扩展板1

    HDU-EID-V2-扩展板1是一款专为STM32微控制器设计的硬件扩展板,主要用于增强核心板的功能。该扩展板具有多种接口和功能,包括ADC(模数转换器)、电位器、DAC(数模转换器)输出以及TEST_V跳线,能够满足用户在模拟...

    ACM HDU 2000-2099 解题报告 杭电 ACM

    《ACM HDU 2000-2099 解题报告 杭电 ACM》是一份详尽的编程竞赛解题集,主要涵盖了杭电(Hangzhou Dianzi University)在线判题系统(HDU OJ)上的2000至2099号题目。这份解题报告是针对参与ACM/ICPC(国际大学生...

    hdu-page-11-answer.rar_hdu_hdu oj第十一页_page_搜题_杭电oj

    "HDU Page 11 Answer"提供的题解资源,不仅节省了逐一搜索题解的时间,还提供了一次性获取多题答案的机会。通过对比不同解法,学习者可以开阔思路,理解多种解决问题的角度,进一步提升编程素养。 总之,"HDU Page ...

    HDU-Coder-X#Daily-question-of-Leetcode#2021-09-24-430. 扁平化多级双向链表

    示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入

    hdu1250高精度加法

    - 使用循环计算出F(n)的值,这里使用了三次高精度加法。 - 最后读取输入的n值,并输出对应的F(n)。 #### 高精度加法详解 高精度加法的基本思想是从低位到高位依次相加,同时记录进位情况。具体的步骤如下: 1. *...

    HDU-Coder-X#Daily-question-of-Leetcode#2022-04-04-307. 区域和检索 - 数

    其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和

    HDU-Coder-X#Daily-question-of-Leetcode#2021-12-12-709. 转换成小写字母1

    示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =

    HDU-Coder-X#Daily-question-of-Leetcode#2022-02-26-2016. 增量元素之间的最

    2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]

    HDU ACMSteps-Chapter One-Section One答案集修正版

    杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh

Global site tag (gtag.js) - Google Analytics