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
分享到:
相关推荐
在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...
这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、答案以及解题思路,对于学习算法和提升编程能力具有很高的价值。 在这个范围内,我们可以预见到涵盖的算法类型可能包括但不限于:...
hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo
《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...
这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些题目涵盖了初级到高级的各种算法,对于学习和提升编程技能非常有帮助。 首先,我们来看看这些题目可能涉及到的基础知识...
【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...
《2019-hdu-multi-(2019杭电多校第二场数据与标程).zip》是一个专门针对编程竞赛爱好者和ACM(国际大学生程序设计竞赛)参赛者的资源包。这个压缩文件的核心内容是2019年杭州电子科技大学(HDU)主办的多校联合...
标题中的"HDU-1535-.zip_多源点"表明这是一个关于解决 ACM (国际大学生程序设计竞赛)问题的程序代码包,问题编号为 HDU 1535,且该问题涉及到多源点的最短路径计算。描述中提到的"求多源点到单终点的最短路(反向...
HDU-EID-V2-扩展板1是一款专为STM32微控制器设计的硬件扩展板,主要用于增强核心板的功能。该扩展板具有多种接口和功能,包括ADC(模数转换器)、电位器、DAC(数模转换器)输出以及TEST_V跳线,能够满足用户在模拟...
《ACM HDU 2000-2099 解题报告 杭电 ACM》是一份详尽的编程竞赛解题集,主要涵盖了杭电(Hangzhou Dianzi University)在线判题系统(HDU OJ)上的2000至2099号题目。这份解题报告是针对参与ACM/ICPC(国际大学生...
"HDU Page 11 Answer"提供的题解资源,不仅节省了逐一搜索题解的时间,还提供了一次性获取多题答案的机会。通过对比不同解法,学习者可以开阔思路,理解多种解决问题的角度,进一步提升编程素养。 总之,"HDU Page ...
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
- 使用循环计算出F(n)的值,这里使用了三次高精度加法。 - 最后读取输入的n值,并输出对应的F(n)。 #### 高精度加法详解 高精度加法的基本思想是从低位到高位依次相加,同时记录进位情况。具体的步骤如下: 1. *...
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh